fork download
copy 
  1. // 50 points subtask for "Bear and Shuffled Points", by Errichto
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. long long ans[1000*1005];
  5. long long sq(long long a) { return a * a; }
  6. struct P {
  7. 	int x, y;
  8. 	long long dist(const P & other) {
  9. 		return sq(x - other.x) + sq(y - other.y);
  10. 	}
  11. 	long long cross(const P & B, const P & C) {
  12. 		return (long long) (B.x - x) * (C.y - y)
  13. 			- (long long) (B.y - y) * (C.x - x);
  14. 	}
  15. 	bool convex(P & B, P & C) { return cross(B, C) < 0; }
  16. };
  17. vector<P> CH(vector<P> w) {
  18. 	if((int) w.size() == 1) return w;
  19.  
  20. 	// find the convex hull
  21. 	vector<P> hull;
  22. 	for(int rep = 0; rep < 2; ++rep) {
  23. 		int rep_hack = hull.size();
  24. 		for(P C : w) {
  25. 			while((int) hull.size() >= rep_hack + 2) {
  26. 				P & A = hull[hull.size() - 2];
  27. 				P & B = hull[hull.size() - 1];
  28. 				if(A.convex(B, C)) break;
  29. 				hull.pop_back();
  30. 			}
  31. 			hull.push_back(C);
  32. 		}
  33. 		hull.pop_back();
  34. 		reverse(w.begin(), w.end());
  35. 	}
  36. 	return hull;
  37. }
  38.  
  39. int main() {
  40. 	int n;
  41. 	scanf("%d", &n);
  42. 	long long ans = 0;
  43. 	vector<P> hull;
  44. 	for(int i = 0; i < n; ++i) {
  45. 		int x, y;
  46. 		scanf("%d%d", &x, &y);
  47. 		P a = P{x, y};
  48. 		for(P p : hull) ans = max(ans, p.dist(a));
  49. 		hull.push_back(a);
  50. 		printf("%lld\n", ans);
  51. 		sort(hull.begin(), hull.end(), [](P & a, P & b) {
  52. 			return make_pair(a.x, a.y) < make_pair(b.x, b.y); });
  53. 		hull = CH(hull);
  54. 	}
  55. }
  56.  
Success #stdin #stdout 0s 11320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
0
0
0
0
0
https://ideone.com/Oj90Lw
language:
C++14 (gcc 8.3)
created:
7 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!