fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ld long double
  4. #define mod 1000000007
  5. #define pb push_back
  6. #define x first
  7. #define y second
  8. #define pt pair<ll,ll>
  9. #define prec(x) fixed << setprecision(x)
  10. using namespace std;
  11.  
  12. ll n;
  13. vector<pt > pts;
  14. vector<ld > angs;
  15. pair<ld,ld> cc;
  16. vector<ll> prefArea;
  17. vector<ll> prefPts;
  18.  
  19. ld f(ld ang){return ((ang * 180.0) / acos(-1.L));}
  20. ld calcAngle(ll x11,ll y11,ld xc,ld yc){
  21. 	ld x1 = (ld)(x11 * 1.0);
  22. 	ld y1 = (ld)(y11 * 1.0);
  23. 	if(x1 == xc){
  24. 		if(y1 > yc){
  25. 			return (ld)(90.0);
  26. 		}
  27. 		else{
  28. 			return (ld)(270.0);
  29. 		}
  30. 	}
  31. 	if(y1 == yc){
  32. 		if(x1 > xc){
  33. 			return (ld)(0.0);
  34. 		}
  35. 		else{
  36. 			return (ld)(180.0);
  37. 		}
  38. 	}
  39. 	if(x1 > xc){
  40. 		if(y1 > yc){
  41. 			ld angle = f(atan((ld)(y1 - yc) / (ld)(x1 - xc)));
  42. 			return angle;
  43. 		}
  44. 		else{
  45. 			ld angle = (ld)(360.0) - f(atan((ld)(yc - y1) / (ld)(x1 - xc)));
  46. 			return angle;
  47. 		}
  48. 	}
  49. 	if(x1 < xc){
  50. 		if(y1 > yc){
  51. 			ld angle = (ld)(180.0) - f(atan((ld)(y1 - yc) / (ld)(xc - x1)));
  52. 			return angle;
  53. 		}
  54. 		else{
  55. 			ld angle = (ld)(180.0) + f(atan((ld)(yc - y1) / (ld)(xc - x1)));
  56. 			return angle;
  57. 		}
  58. 	}
  59. 	return 0.0;
  60. }
  61. ll numOfPtsOnALine(ll x1,ll y1,ll x2,ll y2){
  62. 	if(x1 == x2 && y1 == y2) return 0LL;
  63. 	if(x1 == x2){
  64.         if(y2 < y1) swap(y1,y2);
  65.         return (y2 - y1);
  66.     }
  67.     if(y1 == y2){
  68.         if(x2 < x1) swap(x1,x2);
  69.         return (x2 - x1);
  70.     }
  71.     ll dx = abs(x2 - x1);
  72.     ll dy = abs(y2 - y1);
  73.     return __gcd(dx,dy);
  74. }
  75. ll f(ll x1,ll y1,ll x2,ll y2){
  76. 	// cout << x1 << " " << y1 << " " << x2 << " " << y2 << " --->>>\n";
  77.     if(x1 == x2){
  78.         if(y2 < y1) swap(y1,y2);
  79.         return (y2 - y1 + 1);
  80.     }
  81.     if(y1 == y2){
  82.         if(x2 < x1) swap(x1,x2);
  83.         return (x2 - x1 + 1);
  84.     }
  85.     ll dx = abs(x2 - x1);
  86.     ll dy = abs(y2 - y1);
  87.     return __gcd(dx,dy) + 1;
  88. }
  89. ll myFunc(vector<pt> v){
  90. 	ll n = v.size() - 1;
  91. 	v.erase(v.begin());
  92. 	v.pb(v[0]);
  93. 	ll area = 0;
  94. 	ll pp = 0;
  95. 	// cout << "----------------\n";
  96. 	for(ll i = 0;i < n;i++){
  97. 		// cout << v[i].x << " " << v[i].y << "\n";
  98. 		area = area + (v[i + 1].x * v[i].y - v[i + 1].y * v[i].x);
  99. 		pp = pp + f(v[i].x,v[i].y,v[i + 1].x,v[i + 1].y);
  100. 	}
  101. 	// cout << "-----------------\n";
  102. 	area = abs(area);
  103. 	// cout << "AREA : " << area << "\n";
  104. 	pp = pp - n;
  105. 	// cout << " POINTS : " << pp << "\n";
  106. 	ll ret = abs((area - pp + 2) / 2);
  107. 	return ret;
  108. }
  109. int main(){
  110. 	ios_base::sync_with_stdio(false);
  111. 	cin.tie(NULL);
  112.  
  113. 	cin >> n;
  114.  
  115. 	vector<pt> temppts;
  116. 	temppts.pb({-1,-1});
  117.  
  118. 	cout << prec(8);
  119.  
  120. 	cc.x = (ld)(0.0);
  121. 	cc.y = (ld)(0.0);
  122. 	for(ll i = 1;i <= n;i++){
  123. 		ll tmpx,tmpy;
  124. 		cin >> tmpx >> tmpy;
  125. 		cc.x = cc.x + tmpx * 1.0;
  126. 		cc.y = cc.y + tmpy * 1.0;
  127. 		temppts.pb({tmpx,tmpy});
  128. 	}
  129.  
  130. 	cc.x = (cc.x) / (ld)(n * 1.0);
  131. 	cc.y = (cc.y) / (ld)(n * 1.0);
  132.  
  133. 	set<pair<ld,pt> > ss;
  134. 	set<pt> allPoints;
  135.  
  136. 	for(ll i = 1;i <= n;i++){
  137. 		ss.insert({calcAngle(temppts[i].x,temppts[i].y,cc.x,cc.y),temppts[i]});
  138. 		allPoints.insert(temppts[i]);
  139. 	}
  140.  
  141. 	pts.pb({-1,-1});	// 1 based indexing
  142. 	angs.pb(-1);
  143. 	for(auto z : ss){
  144. 		pts.pb(z.y);
  145. 		angs.pb(z.x);
  146. 	}
  147. 	ll NUMOFPOINTS = myFunc(pts);
  148. 	// cout << "NUMOFPOINTS -> " << NUMOFPOINTS << "\n";
  149. 	pts.pb(pts[1]);
  150.  
  151. 	prefPts.pb(0);
  152. 	prefArea.pb(0);
  153.  
  154. 	for(ll i = 1;i <= n;i++){
  155. 		prefArea.pb(prefArea[i - 1] + (pts[i + 1].x * pts[i].y - pts[i + 1].y * pts[i].x));
  156. 		prefPts.pb(prefPts[i - 1] + numOfPtsOnALine(pts[i].x,pts[i].y,pts[i + 1].x,pts[i + 1].y));
  157. 	}
  158. 	/*
  159. 	cout << "PRINTING THE ANGLES : \n";
  160. 	for(auto x : angs){
  161. 		cout << x << "\n";
  162. 	}
  163. 	cout << "--------------------------\n";
  164. 	cout << "PRINTING THE AREA ARRAY : \n";
  165. 	ll oo = 0;
  166. 	for(auto z : prefArea){
  167. 		cout << pts[oo].x << " " << pts[oo].y << " " << z << "\n";
  168. 		oo++;
  169. 	}
  170. 	cout << "-------------------------\n";
  171. 	cout << "PRINTING THE POINTS ARRAY : \n";
  172. 	oo = 0;
  173. 	for(auto x : prefPts){
  174. 		cout << oo << " " << x << "\n";
  175. 		oo++;
  176. 	}
  177. 	cout << "-------------------------\n";
  178. 	*/
  179. 	ll q;
  180. 	cin >> q;
  181. 	while(q--){
  182. 		pt p,q;
  183. 		cin >> p.x >> p.y >> q.x >> q.y;
  184. 		ld pang = calcAngle(p.x,p.y,cc.x,cc.y);
  185. 		ld qang = calcAngle(q.x,q.y,cc.x,cc.y);
  186. 		if(qang < pang){
  187. 			swap(p,q);
  188. 			swap(pang,qang);
  189. 		}
  190. 		// cout << "chhota angle " << pang << " bada angle " << qang << "\n";
  191. 		ll pidx;
  192. 		auto pit = lower_bound(angs.begin(),angs.end(),pang);
  193. 		pidx = (pit - angs.begin());
  194. 		ll qidx;
  195. 		auto qit = lower_bound(angs.begin(),angs.end(),qang);
  196. 		if(*(qit) != qang) qit--;
  197. 		qidx = (qit - angs.begin());
  198.  
  199. 		pt fpt = pts[pidx];
  200. 		pt bpt = pts[qidx];
  201. 		// cout << "FPT x " << fpt.x << " y " << fpt.y << "\n";
  202. 		// cout << "BPT x " << bpt.x << " y " << bpt.y << "\n";
  203.  
  204. 		ll area = prefArea[qidx - 1] - prefArea[pidx - 1];
  205. 		area += fpt.x * p.y - fpt.y * p.x;
  206. 		area += q.x * bpt.y - q.y * bpt.x;
  207. 		area += p.x * q.y - q.x * p.y;
  208.  
  209.  
  210. 		ll ppts = prefPts[qidx - 1] - prefPts[pidx - 1];
  211. 		// cout << ppts << " !!!!!!!!!!!\n";
  212.  
  213. 		if(allPoints.find(p) == allPoints.end())
  214. 			ppts += numOfPtsOnALine(fpt.x,fpt.y,p.x,p.y);
  215. 		// cout << ppts << " !!!!!!!!!!!\n";
  216.  
  217. 		ppts += numOfPtsOnALine(p.x,p.y,q.x,q.y);
  218. 		// cout << ppts << " !!!!!!!!!!!\n";
  219.  
  220. 		if(allPoints.find(q) == allPoints.end())
  221. 			ppts += numOfPtsOnALine(bpt.x,bpt.y,q.x,q.y);
  222. 		// cout << ppts << " !!!!!!!!!!!\n";
  223.  
  224. 		// cout << pidx << " " << qidx << "\n";
  225. 		// cout << "AREA = " << area << " PERIMETER POINTS = " << ppts << "\n";
  226.  
  227. 		ll ans = (abs(area) - ppts + 2) / 2;
  228. 		ll tempwa = NUMOFPOINTS - numOfPtsOnALine(p.x,p.y,q.x,q.y) + 1;
  229. 		cout << min(ans,tempwa - ans) << " " << max(ans,tempwa - ans) << "\n"; 
  230.  
  231. 	}
  232.  
  233. 	return 0;
  234. }
Success #stdin #stdout 0s 4376KB
comments (?)
stdin
copy 
6
1 6
0 3
2 0   
8 1
13 5
4 8
1
2 0 7 7
stdout
copy 
26 34
https://ideone.com/j06NN7
language:
C++14 (clang 8.0)
created:
4 years ago
visibility:
public

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!