fork download
  1. // Cake, by Errichto
  2. // intended, O(n)
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. #define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
  6. #define RI(i,n) FOR(i,1,(n))
  7. #define REP(i,n) FOR(i,0,(n)-1)
  8. typedef long long ll;
  9.  
  10. const int nax = 1e6 + 15;
  11. const int mod = 1e9 + 7;
  12.  
  13. struct P {
  14. ll x, y;
  15. ll operator * (const P & b) const {
  16. return -x * b.y + y * b.x;
  17. }
  18. } t[nax];
  19.  
  20. ll sum_x, sum_y, sum_product, sum_product2;
  21.  
  22. void makeMod() {
  23. // sum_x %= mod;
  24. // sum_y %= mod;
  25. // sum_product %= mod;
  26. sum_product2 %= mod;
  27. }
  28.  
  29. void insert(int i) {
  30. sum_x += t[i].x;
  31. sum_y += t[i].y;
  32. sum_product += t[i-1] * t[i];
  33. sum_product2 += (t[i-1] * t[i]) % mod * i;
  34. makeMod();
  35. }
  36. void remove(int i) {
  37. sum_x -= t[i].x;
  38. sum_y -= t[i].y;
  39. sum_product -= t[i] * t[i+1];
  40. sum_product2 -= (t[i] * t[i+1]) % mod * (i + 1);
  41. makeMod();
  42. }
  43.  
  44. int main() {
  45. int n;
  46. scanf("%d", &n);
  47. REP(i, n) scanf("%lld%lld", &t[i].x, &t[i].y);
  48. REP(i, n+2) t[i+n] = t[i];
  49. ll total = 0;
  50. REP(i, n) total += t[i] * t[i+1];
  51. assert(total > 0);
  52. int b = 0;
  53. sum_x = t[0].x;
  54. sum_y = t[0].y;
  55. ll ans = 0;
  56. REP(a, n) {
  57. while(true) {
  58. unsigned long long tmp = 2 * (sum_product + (unsigned long long)( t[b] * t[b+1]) + (unsigned long long) (t[b+1] * t[a]));
  59. if(tmp < (unsigned long long)total || (tmp == (unsigned long long)total && b + 1 < n)) {
  60. insert(b + 1);
  61. ++b;
  62. }
  63. else break;
  64. }
  65. ll tmp = sum_product % mod * (b + 1) - sum_product2;
  66. tmp %= mod;
  67. P fake = P{sum_x % mod, sum_y % mod};
  68. tmp += fake * t[a];
  69. ans += tmp;
  70. ans %= mod;
  71. remove(a);
  72. }
  73. ans = (ll) n * (n - 3) / 2 % mod * (total % mod) - 2 * ans;
  74. ans = (ans % mod + mod) % mod;
  75. printf("%lld\n", ans);
  76. return 0;
  77. }
Time limit exceeded #stdin #stdout 5s 19088KB
stdin
Standard input is empty
stdout
Standard output is empty