fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define int long long
  5. #define double long double
  6. ll nCr(ll n,ll r)
  7. {
  8.     ll ret=1;
  9.     for(ll i=r+1;i<=n;i++)
  10.     {
  11.         ret*=i;
  12.         ret/=(i-r);
  13.     }
  14.     return ret;
  15. }
  16. struct point{
  17.     int x,y;
  18. };
  19. bool double_compare(double a,double b)
  20. {
  21.     double EPS=1e-12;
  22.     if(fabs(a-b)<=EPS)
  23.     {
  24.         return 1;
  25.     }
  26.     return 0;
  27. }
  28. double mail(point a,point b)
  29. {
  30.     if(a.x==b.x) return 1e10;
  31.     return 1.0*(a.y-b.y)/(a.x-b.x);
  32. }
  33. bool is_same_line(point a,point b,point c)
  34. {
  35.     double s[]={mail(a,b),mail(b,c),mail(a,c)};
  36.     return (double_compare(s[0],s[2])&&double_compare(s[0],s[1])&&double_compare(s[1],s[2]));
  37. }
  38. signed main()
  39. {
  40.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  41.     int n;cin>>n;
  42.     if(n<4)
  43.     {
  44.         cout<<0;
  45.         return 0;
  46.     }
  47.     ll ans=nCr(n,4);
  48.     map<multiset<int>,int>vis;
  49.     point s[n];
  50.     for(int i=0;i<n;i++)
  51.     {
  52.         cin>>s[i].x>>s[i].y;
  53.     }
  54.     for(int i=0;i<n-2;i++)
  55.     {
  56.         for(int o=i+1;o<n-1;o++)
  57.         {
  58.             for(int p=o+1;p<n;p++)
  59.             {
  60.                 if(is_same_line(s[i],s[o],s[p]))
  61.                 {
  62.                     ans-=n-3-max({vis[{i,o}],vis[{i,p}],vis[{p,o}]});
  63.                     vis[{i,o}]++;
  64.                     vis[{i,p}]++;
  65.                     vis[{p,o}]++;
  66.                 }
  67.             }
  68.         }
  69.     }
  70.     cout<<ans;
  71.     return 0;
  72. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
10
0 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
1 0
1 5
stdout
copy 
28
https://ideone.com/b5i9Zq
language:
C++14 (gcc 8.3)
created:
89 days 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!