fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5.  
  6. const int N = 318;
  7.  
  8. struct point {
  9.     int x,y;
  10.     int idx;
  11.     int code;
  12.     point(){}
  13.     point(int a, int b, int c) {
  14.         x=a;
  15.         y=b;
  16.         idx=c;
  17.     }
  18. };
  19.  
  20. int tests,current_case;
  21. int n;
  22. point a[N];
  23. int ans[N];
  24. point pta,ptb;
  25. point good[N];
  26. int sz;
  27. int c3[N],c1[N],c1c3[N];
  28. set < point > s;
  29. int all;
  30. int it[N];
  31.  
  32. void message(int current_case) {
  33.     //cerr<<"Case "<<current_case<<" solved!"<<endl;
  34.     fprintf(stderr, "Case %d solved!\n", current_case);
  35. }
  36.  
  37. void update(int pos, int val) {
  38.     for(;pos<=all;pos+=pos&(-pos)) it[pos]+=val;
  39. }
  40.  
  41. int query(int pos) {
  42.     --pos;
  43.     int ans=0;
  44.     for(;pos>=1;pos-=pos&(-pos)) ans+=it[pos];
  45.     return ans;
  46. }
  47.  
  48. void compress() {
  49.     sort(good+1,good+1+sz);
  50.     for(int i=1;i<=sz;i++) {
  51.         good[i].code=i;
  52.     }
  53. }
  54.  
  55. int count_less(point a) {
  56.     return query(a.code);
  57. }
  58.  
  59. long long oriented_area(point a, point b, point c) {
  60.     return ((a.x-b.x)*1ll*(a.y+b.y) + (b.x-c.x)*1ll*(b.y+c.y) + (c.x-a.x)*1ll*(c.y+a.y));
  61. }
  62.  
  63. long long area(point a, point b, point c) {
  64.     return abs(oriented_area(a,b,c));
  65. }
  66.  
  67. bool operator <(const point &a, const point &b) {
  68.     return oriented_area(ptb,b,a)>0;
  69. }
  70.  
  71. int prcmp(point a, point b) {
  72.     return make_pair(a.x,a.y)<make_pair(b.x,b.y);
  73. }
  74.  
  75. bool cmpa(point a, point b) {
  76.     return oriented_area(pta,a,b)<0;
  77. }
  78.  
  79. void solve() {
  80.     sz=0;
  81.     int i;
  82.     for(i=1;i<=n;i++) if(oriented_area(pta,ptb,a[i])>0 && prcmp(pta,a[i])) {
  83.         good[++sz]=a[i];
  84.     }
  85.     compress();
  86.     all=sz;
  87.     for(i=1;i<=sz;i++) c1c3[good[i].idx]=i-1;
  88.     for(i=1;i<=all;i++) it[i]=0;
  89.     sort(good+1,good+1+sz,cmpa);
  90.     for(i=1;i<=sz;i++) {
  91.         c3[good[i].idx]=count_less(good[i]);
  92.         update(good[i].code,1);
  93.         c1[good[i].idx]=c1c3[good[i].idx]-c3[good[i].idx];
  94.         ++ans[c1[good[i].idx]];
  95.     }
  96. }
  97.  
  98. int main() {
  99.     //ios_base::sync_with_stdio(false);
  100.     //cin.tie(NULL);
  101.     freopen("triangles.in","r",stdin);
  102.     freopen("triangles.out","w",stdout);
  103.     int i,j;
  104.  
  105.     tests=1;
  106.     //scanf("%d", &tests);
  107.     //cin>>tests;
  108.     for(current_case=1;current_case<=tests;current_case++) {
  109.         scanf("%d", &n);
  110.         for(i=1;i<=n;i++) {
  111.             scanf("%d %d", &a[i].x, &a[i].y);
  112.             a[i].idx=i;
  113.         }
  114.         memset(ans,0,sizeof(ans));
  115.         for(i=1;i<=n;i++) {
  116.             for(j=1;j<=n;j++) {
  117.                 pta=a[i];
  118.                 ptb=a[j];
  119.                 if(!prcmp(pta,ptb)) continue;
  120.                 solve();
  121.             }
  122.         }
  123.         for(i=0;i<=n-3;i++) {
  124.             printf("%d\n", ans[i]);
  125.         }
  126.  
  127.         MESSAGE:
  128.         message(current_case);
  129.     }
  130.  
  131.     return 0;
  132. }
Success #stdin #stdout #stderr 0s 3488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Case 1 solved!
https://ideone.com/BjIYW3
language:
C++14 (gcc 8.3)
created:
7 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!