fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/RUY5lF
Cake
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!