Advertisement
Guest User

Untitled

a guest
Jun 18th, 2015
532
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.90 KB | None | 0 0
  1. #include <cassert>
  2. #include <cctype>
  3. #include <climits>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <sstream>
  10. #include <iomanip>
  11. #include <string>
  12. #include <vector>
  13. #include <list>
  14. #include <set>
  15. #include <map>
  16. #include <stack>
  17. #include <queue>
  18. #include <algorithm>
  19. #include <iterator>
  20. #include <utility>
  21. using namespace std;
  22.  
  23. #define MP(x, y) make_pair(x, y)
  24. #define SET(p) memset(p, -1, sizeof(p))
  25. #define CLR(p) memset(p, 0, sizeof(p))
  26. #define MEM(p, v) memset(p, v, sizeof(p))
  27. #define CPY(d, s) memcpy(d, s, sizeof(s))
  28. #define SZ(c) (int)c.size()
  29. #define PB(x) push_back(x)
  30. #define ff first
  31. #define ss second
  32. #define ll long long
  33. #define ld long double
  34. #define mod 1000000007
  35. #define inf 1000000000
  36. typedef pair< double, double > pii;
  37. typedef pair< int, int > pll;
  38. typedef pair< string, int > psi;
  39. vector <pii> pnts;
  40. map <pii,ll> line;
  41. bool comp(pii a,pii b){
  42.     double x = a.ss/a.ff;
  43.     double y = b.ss/b.ff;
  44.     if(x==y)return (a.ff*a.ff + a.ss*a.ss) < (b.ff*b.ff + b.ss*b.ss) ;
  45.     return x<y;
  46. }
  47. ll solve(){
  48.     sort(pnts.begin(),pnts.end(),comp);
  49.     for(int i=0;i<pnts.size();i++){
  50.         for(int j=i+1;j<pnts.size();j++){
  51.             double m = (pnts[j].ss-pnts[i].ss)/(pnts[j].ff-pnts[i].ff);
  52.             double c = (pnts[i].ss*pnts[j].ff-pnts[i].ff*pnts[j].ss)/(pnts[j].ff-pnts[i].ff);
  53.             if(pnts[i].ff==pnts[j].ff){
  54.                 c=pnts[i].ff;
  55.             }
  56.             line[MP(m,c)]++;
  57.         }
  58.     }
  59.     ll ans=0;
  60.     for(map <pii,ll>::iterator it = line.begin();it!=line.end();it++){
  61.         if(it->second){
  62.             ll tem = it->second;
  63.             ll x = 1+sqrt(1+8*tem);
  64.             x/=2;
  65.             //cout<<tem<<" "<<x<<endl;
  66.             ans+=((x*(x-1)*(x-2))/6);
  67.         }
  68.     }
  69.     //cout<<ans<<endl;
  70.     return ans;
  71. }
  72. int main(int argc, char const *argv[])
  73. {
  74.     ll n;
  75.     cin>>n;
  76.     ll ans = ((n*(n-1)*(n-2))/6);
  77.     for(int i=0;i<n;i++){
  78.         double x,y;
  79.         cin>>x>>y;
  80.         pnts.PB(MP(x+101,y+101));
  81.     }
  82.     ans-=solve();
  83.     cout<<ans<<endl;
  84. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement