fork download
copy 
  1. #include<stdio.h>
  2. #include<map>
  3. #include<string>
  4. using namespace std;
  5. struct xy { long long x, y; }a[212];;
  6. int ccw(xy a, xy b, xy c) {
  7. 	return a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x > 0;
  8. }
  9. int jd(int x) { if (x < 0)return -x; return x; }
  10. int dist(xy a, xy b) { return jd(a.x - b.x) + jd(a.y - b.y); }
  11. bool flag[212];
  12. int S[212];
  13. int max(int a, int b) { if (a < b)return b; return a; }
  14. int min(int a, int b) { if (a < b)return a; return b; }
  15. map<string, int>M;
  16. int main() {
  17. 	int n, i, j;
  18. 	scanf("%d", &n);
  19. 	for (i = 0; i < n; i++)scanf("%lld%lld", &a[i].x, &a[i].y);
  20. 	for (i = 1; i < n; i++)flag[i] = ccw(a[(i + n - 1) % n], a[i], a[(i + 1) % n]);
  21. 	for (i = 1; i < n; i++) {
  22. 		string temp = "";
  23. 		for (j = i; j != 0; j = (j + 1) % n) {
  24. 			temp = temp + (flag[j] ? "a" : "b");
  25. 			M[temp] = M[temp] + 1;
  26. 			int k = jd(dist(a[j], a[(j + 1) % n]));
  27. 			while (k > 0)temp += k % 10, k /= 10;
  28. 		}
  29. 	}
  30. 	for (i = 1; i <= n; i++)S[i%n] = S[(i + n - 1) % n] + dist(a[(i + n - 1) % n], a[i%n]);
  31. 	int ans = 0;
  32. 	for (i = 1; i < n; i++) {
  33. 		string temp = "";
  34. 		int now = 0;
  35. 		for (j = i; j != 0; j = (j + 1) % n) {
  36. 			temp = temp + (flag[j] ? "a" : "b");
  37. 			if (M[temp] == 1) {
  38. 				now += min(S[0] - S[j], S[j]);
  39. 				break;
  40. 			}
  41. 			int k = jd(dist(a[j], a[(j + 1) % n]));
  42. 			now += k;
  43. 			while (k > 0)temp += k % 10, k /= 10;
  44. 		}
  45. 		ans = max(ans,now- min(S[i], S[0] - S[i]));
  46. 	}
  47. 	printf("%d", ans);
  48. 	return 0;
  49. }
Success #stdin #stdout 0s 4500KB
comments (?)
stdin
copy 
4
0 0
0 10
1 10
1 0
stdout
copy 
2
https://ideone.com/44Vu9c
language:
C++14 (gcc 8.3)
created:
6 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!