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.     point(){}
  12.     point(int a, int b, int c) {
  13.         x=a;
  14.         y=b;
  15.         idx=c;
  16.     }
  17. };
  18.  
  19. int tests,current_case;
  20. int n;
  21. point a[N];
  22. int ans[N];
  23. point pta,ptb;
  24. point good[N];
  25. int sz;
  26. int c3[N],c1[N],c1c3[N];
  27. set < point > s;
  28. map < point, int > code;
  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.     code.clear();
  50.     sort(good+1,good+1+sz);
  51.     for(int i=1;i<=sz;i++) {
  52.         code[good[i]]=i;
  53.     }
  54. }
  55.  
  56. int count_less2(point a) {
  57.     return query(code[a]);
  58. }
  59.  
  60. long long oriented_area(point a, point b, point c) {
  61.     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));
  62. }
  63.  
  64. long long area(point a, point b, point c) {
  65.     return abs(oriented_area(a,b,c));
  66. }
  67.  
  68. bool operator <(const point &a, const point &b) {
  69.     return oriented_area(ptb,b,a)>0;
  70. }
  71.  
  72. bool cmpa(point a, point b) {
  73.     return oriented_area(pta,a,b)<0;
  74. }
  75.  
  76. int count_less(point a) {
  77.     int ans;
  78.     set < point >::iterator it;
  79.     s.insert(a);
  80.     it=s.find(a);
  81.     ans=distance(s.begin(),it);
  82.     s.erase(it);
  83.     return ans;
  84. }
  85.  
  86. void solve() {
  87.     sz=0;
  88.     int i;
  89.     for(i=1;i<=n;i++) if(oriented_area(pta,ptb,a[i])>0) {
  90.         good[++sz]=a[i];
  91.     }
  92.     compress();
  93.     all=sz;
  94.     sort(good+1,good+1+sz);
  95.     for(i=1;i<=sz;i++) c1c3[good[i].idx]=i-1;
  96.     s.clear();
  97.     memset(it,0,sizeof(it));
  98.     sort(good+1,good+1+sz,cmpa);
  99.     for(i=1;i<=sz;i++) {
  100.         c3[good[i].idx]=count_less2(good[i]);
  101.         //s.insert(good[i]);
  102.         update(code[good[i]],1);
  103.         c1[good[i].idx]=c1c3[good[i].idx]-c3[good[i].idx];
  104.         ++ans[c1[good[i].idx]];
  105.     }
  106. }
  107.  
  108. int main() {
  109.     //ios_base::sync_with_stdio(false);
  110.     //cin.tie(NULL);
  111.     freopen("triangles.in","r",stdin);
  112.     freopen("triangles.out","w",stdout);
  113.     int i,j;
  114.  
  115.     tests=1;
  116.     //scanf("%d", &tests);
  117.     //cin>>tests;
  118.     for(current_case=1;current_case<=tests;current_case++) {
  119.         scanf("%d", &n);
  120.         for(i=1;i<=n;i++) {
  121.             scanf("%d %d", &a[i].x, &a[i].y);
  122.             a[i].idx=i;
  123.         }
  124.         memset(ans,0,sizeof(ans));
  125.         for(i=1;i<=n;i++) {
  126.             for(j=1;j<=n;j++) {
  127.                 if(i==j) continue;
  128.                 pta=a[i];
  129.                 ptb=a[j];
  130.                 solve();
  131.             }
  132.         }
  133.         for(i=0;i<=n-3;i++) {
  134.             printf("%d\n", ans[i]/3);
  135.         }
  136.  
  137.         MESSAGE:
  138.         message(current_case);
  139.     }
  140.  
  141.     return 0;
  142. }
  143.  
Success #stdin #stdout #stderr 0s 3492KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Case 1 solved!
https://ideone.com/EqZeS2
language:
C++14 (gcc 8.3)
created:
8 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!