fork download
copy 
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <string>
  9. #include <queue>
  10. #include <stack>
  11. #include <algorithm>
  12. #include <cmath>
  13. #include <iomanip>
  14. #define dibs reserve
  15. #define OVER9000 1234567890
  16. #define patkan 9
  17. #define tisic 47
  18. #define soclose 1e-9
  19. #define pi 3.1415926535898
  20. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  21. #define chocolate win
  22. #define ff first
  23. #define ss second
  24. #define abs(x) ((x < 0)?-(x):(x))
  25. #define uint unsigned int
  26. // mylittlepony
  27. using namespace std;
  28.  
  29. struct point {
  30. 	long long x,y;
  31.  
  32. 	bool operator<(const point &P) const {
  33. 		if(x != P.x) return x < P.x;
  34. 		return y < P.y;}
  35. 	};
  36.  
  37. int sig(long long x) {
  38. 	if(x > 0) return 1;
  39. 	if(x == 0) return 0;
  40. 	return -1;}
  41.  
  42. long long vs(point A, point B, point O) {
  43. 	return (A.x-O.x)*(B.y-O.y)-(A.y-O.y)*(B.x-O.x);}
  44.  
  45. int main() {
  46. //	freopen("curling.in","r",stdin);
  47. //	freopen("curling.out","w",stdout);
  48. 	int N;
  49. 	scanf(" %d",&N);
  50. 	vector<point> P[2];
  51. 	for(int i =0; i < 2; i++) {
  52. 		P[i].resize(N);
  53. 		for(int j =0; j < N; j++) scanf(" %lld %lld",&P[i][j].x,&P[i][j].y);}
  54.  
  55. 	vector<point> H[2][2];
  56. 	for(int k =0; k < 2; k++) {
  57. 		sort(P[k].begin(),P[k].end());
  58. 		H[k][0].push_back(P[k][0]); // body nad
  59. 		H[k][1].push_back(P[k][0]); // body pod
  60. 		for(int i =1; i < N; i++) {
  61. 			if(vs(P[k][N-1],P[k][i],P[k][0]) >= 0) {
  62. 				while(H[k][0].size() > 1 && vs(*H[k][0].rbegin(),P[k][i],H[k][0][H[k][0].size()-2]) >= 0)
  63. 					H[k][0].pop_back();
  64. 				H[k][0].push_back(P[k][i]);}
  65. 			if(vs(P[k][N-1],P[k][i],P[k][0]) <= 0) {
  66. 				while(H[k][1].size() > 1 && vs(*H[k][1].rbegin(),P[k][i],H[k][1][H[k][1].size()-2]) <= 0)
  67. 					H[k][1].pop_back();
  68. 				H[k][1].push_back(P[k][i]);}
  69. 			}
  70. //		for(int i =0; i < H[k][0].size(); i++) cout << H[k][0][i].x << " " << H[k][0][i].y << " " << k << " " << 0 << "\n";
  71. //		for(int i =0; i < H[k][1].size(); i++) cout << H[k][1][i].x << " " << H[k][1][i].y << " " << k << " " << 1 << "\n";
  72. 		}
  73.  
  74. 	for(int k =1; k >= 0; k--) {
  75. 		int ans =0;
  76.  
  77. 		int L[2] ={0,0}; // priamka nad, pod v kazdej polovici
  78. 		// najpravsi bod nie vpravo od nasho
  79. 		for(int i =0; i < N; i++) {
  80. 			while(L[0] < (int)H[1-k][0].size()-1 && H[1-k][0][L[0]+1].x <= P[k][i].x) L[0]++;
  81. 			while(L[1] < (int)H[1-k][1].size()-1 && H[1-k][1][L[1]+1].x <= P[k][i].x) L[1]++;
  82. 			bool b =false;
  83. 			for(int j =max(0,L[0]-2); j <= min((int)H[1-k][0].size()-2,L[0]+2); j++)
  84. 				if(vs(H[1-k][0][j+1],P[k][i],H[1-k][0][j]) <= 0)
  85. 					if(H[1-k][0][j].x <= P[k][i].x && H[1-k][0][j+1].x >= P[k][i].x) b =true;
  86. 			if(!b) continue;
  87. 			b =false;
  88. 			for(int j =max(0,L[1]-2); j <= min((int)H[1-k][1].size()-2,L[1]+2); j++)
  89. 				if(vs(H[1-k][1][j+1],P[k][i],H[1-k][1][j]) >= 0)
  90. 					if(H[1-k][1][j].x <= P[k][i].x && H[1-k][1][j+1].x >= P[k][i].x) b =true;
  91. 			if(b) ans++;}
  92.  
  93. 		printf("%d",ans);
  94. 		if(k == 1) printf(" ");
  95. 		else printf("\n");}
  96. 	return 0;}
  97.  
  98. // look at my code
  99. // my code is amazing
  100.  
Runtime error #stdin #stdout #stderr 0s 4372KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/6JGzwm
usaco jan14 gold1
language:
C++14 (gcc 8.3)
created:
10 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!