fork download
copy 
  1. #include<stdio.h>
  2. struct xy {long long x, y;}a[313];
  3. int cnt[313][313],ans[313];
  4. long long ccw(xy a, xy b, xy c) {
  5. 	long long k = a.x*b.y + b.x*c.y + c.x*a.y - a.y*b.x - b.y*c.x - c.y*a.x;
  6. 	if (k > 0)return 1;
  7. 	if (k < 0)return -1;
  8. 	return 0;
  9. }
  10. bool is_in(xy a, xy b, xy c,xy d) {
  11. 	int A = ccw(a, b, d), B = ccw(b, c, d), C = ccw(c, a, d);
  12. 	if (!A || !B || !C)return 0;
  13. 	return A == B&& B == C;
  14. }
  15. int jd(int a) { if (a < 0)return -a; return a; }
  16. int main() {
  17. 	int n, i, j, k;
  18. 	xy P = { (long long)1e9,(long long)1e9 };
  19. 	scanf("%d", &n);
  20. 	for (i = 0; i < n; i++) {
  21. 		scanf("%lld%lld", &a[i].x, &a[i].y);
  22. 		if (P.y > a[i].y)P = a[i];
  23. 	}
  24. 	for (i = 0; i < n; i++)for (j = i + 1; j < n; j++)for (k = 0; k < n; k++) {
  25. 		if (is_in(P, a[i], a[j], a[k]))cnt[i][j]++, cnt[j][i]++;
  26. 	}
  27. 	for (i = 0; i < n; i++)for (j = i + 1; j < n; j++)for (k = j + 1; k < n; k++) {
  28. 		int x, flag = 0;
  29. 		if (ccw(P, a[i], a[j]) > 0)i ^= j ^= i ^= j, flag = 1;
  30. 		if (ccw(P, a[i], a[k]) > 0)x = cnt[j][k] - cnt[i][k] - cnt[i][j];
  31. 		else if (ccw(P, a[j], a[k]) < 0)x = cnt[i][k] - cnt[j][k] - cnt[i][j];
  32. 		else x = cnt[i][k] + cnt[j][k] - cnt[i][j];
  33. 		if (flag)i ^= j ^= i ^= j;
  34. 		x = jd(x) - (is_in(P, a[i], a[j], a[k]) || is_in(P, a[j], a[k], a[i]) || is_in(P, a[k], a[i], a[j]));
  35. 		ans[jd(x)]++;
  36. 	}
  37. 	for (i = 0; i < n - 2; i++)printf("%d\n", ans[i]);
  38. 	return 0;
  39. }
Success #stdin #stdout 0s 4324KB
comments (?)
stdin
copy 
7
3 6
17 15
13 15
6 12
9 1
2 7
10 19
stdout
copy 
28
6
1
0
0
https://ideone.com/YmCngz
language:
C++ (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!