fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. void*wmem;
  5. char memarr[96000000];
  6. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  7.   static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  8.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  9.   (*arr)=(T*)(*mem);
  10.   (*mem)=((*arr)+x);
  11. }
  12. template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
  13.   walloc1d(arr, x2-x1, mem);
  14.   (*arr) -= x1;
  15. }
  16. template<class T1, class T2, class T3> void sortA_L(int N, T1 a[], T2 b[], T3 c[], void *mem = wmem){
  17.   int i;
  18.   pair<T1, pair<T2, T3> >*arr;
  19.   walloc1d(&arr, N, &mem);
  20.   for(i=(0);i<(N);i++){
  21.     arr[i].first = a[i];
  22.     arr[i].second.first = b[i];
  23.     arr[i].second.second = c[i];
  24.   }
  25.   sort(arr, arr+N);
  26.   for(i=(0);i<(N);i++){
  27.     a[i] = arr[i].first;
  28.     b[i] = arr[i].second.first;
  29.     c[i] = arr[i].second.second;
  30.   }
  31. }
  32. template<class T1, class T2, class T3, class T4> void sortA_L(int N, T1 a[], T2 b[], T3 c[], T4 d[], void *mem = wmem){
  33.   int i;
  34.   pair<pair<T1, T2>, pair<T3, T4> >*arr;
  35.   walloc1d(&arr, N, &mem);
  36.   for(i=(0);i<(N);i++){
  37.     arr[i].first.first = a[i];
  38.     arr[i].first.second = b[i];
  39.     arr[i].second.first = c[i];
  40.     arr[i].second.second = d[i];
  41.   }
  42.   sort(arr, arr+N);
  43.   for(i=(0);i<(N);i++){
  44.     a[i] = arr[i].first.first;
  45.     b[i] = arr[i].first.second;
  46.     c[i] = arr[i].second.first;
  47.     d[i] = arr[i].second.second;
  48.   }
  49. }
  50. inline int my_getchar_unlocked(){
  51.   static char buf[1048576];
  52.   static int s = 1048576;
  53.   static int e = 1048576;
  54.   if(s == e && e == 1048576){
  55.     e = fread_unlocked(buf, 1, 1048576, stdin);
  56.     s = 0;
  57.   }
  58.   if(s == e){
  59.     return EOF;
  60.   }
  61.   return buf[s++];
  62. }
  63. inline void rd(int &x){
  64.   int k;
  65.   int m=0;
  66.   x=0;
  67.   for(;;){
  68.     k = my_getchar_unlocked();
  69.     if(k=='-'){
  70.       m=1;
  71.       break;
  72.     }
  73.     if('0'<=k&&k<='9'){
  74.       x=k-'0';
  75.       break;
  76.     }
  77.   }
  78.   for(;;){
  79.     k = my_getchar_unlocked();
  80.     if(k<'0'||k>'9'){
  81.       break;
  82.     }
  83.     x=x*10+k-'0';
  84.   }
  85.   if(m){
  86.     x=-x;
  87.   }
  88. }
  89. inline void rd(long long &x){
  90.   int k;
  91.   int m=0;
  92.   x=0;
  93.   for(;;){
  94.     k = my_getchar_unlocked();
  95.     if(k=='-'){
  96.       m=1;
  97.       break;
  98.     }
  99.     if('0'<=k&&k<='9'){
  100.       x=k-'0';
  101.       break;
  102.     }
  103.   }
  104.   for(;;){
  105.     k = my_getchar_unlocked();
  106.     if(k<'0'||k>'9'){
  107.       break;
  108.     }
  109.     x=x*10+k-'0';
  110.   }
  111.   if(m){
  112.     x=-x;
  113.   }
  114. }
  115. struct MY_WRITER{
  116.   char buf[1048576];
  117.   int s;
  118.   int e;
  119.   MY_WRITER(){
  120.     s = 0;
  121.     e = 1048576;
  122.   }
  123.   ~MY_WRITER(){
  124.     if(s){
  125.       fwrite_unlocked(buf, 1, s, stdout);
  126.     }
  127.   }
  128. }
  129. ;
  130. MY_WRITER MY_WRITER_VAR;
  131. void my_putchar_unlocked(int a){
  132.   if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
  133.     fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
  134.     MY_WRITER_VAR.s = 0;
  135.   }
  136.   MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
  137. }
  138. inline void wt_L(char a){
  139.   my_putchar_unlocked(a);
  140. }
  141. inline void wt_L(long long x){
  142.   int s=0;
  143.   int m=0;
  144.   char f[20];
  145.   if(x<0){
  146.     m=1;
  147.     x=-x;
  148.   }
  149.   while(x){
  150.     f[s++]=x%10;
  151.     x/=10;
  152.   }
  153.   if(!s){
  154.     f[s++]=0;
  155.   }
  156.   if(m){
  157.     my_putchar_unlocked('-');
  158.   }
  159.   while(s--){
  160.     my_putchar_unlocked(f[s]+'0');
  161.   }
  162. }
  163. template<class T, class U> inline T GCD_L(T a, U b){
  164.   T r;
  165.   while(b){
  166.     r=a;
  167.     a=b;
  168.     b=r%a;
  169.   }
  170.   return a;
  171. }
  172. template<class S> inline void arrInsert(const int k, int &sz, S a[], const S aval){
  173.   int i;
  174.   sz++;
  175.   for(i=sz-1;i>k;i--){
  176.     a[i] = a[i-1];
  177.   }
  178.   a[k] = aval;
  179. }
  180. template<class S, class T> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval){
  181.   int i;
  182.   sz++;
  183.   for(i=sz-1;i>k;i--){
  184.     a[i] = a[i-1];
  185.   }
  186.   for(i=sz-1;i>k;i--){
  187.     b[i] = b[i-1];
  188.   }
  189.   a[k] = aval;
  190.   b[k] = bval;
  191. }
  192. template<class S, class T, class U> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval){
  193.   int i;
  194.   sz++;
  195.   for(i=sz-1;i>k;i--){
  196.     a[i] = a[i-1];
  197.   }
  198.   for(i=sz-1;i>k;i--){
  199.     b[i] = b[i-1];
  200.   }
  201.   for(i=sz-1;i>k;i--){
  202.     c[i] = c[i-1];
  203.   }
  204.   a[k] = aval;
  205.   b[k] = bval;
  206.   c[k] = cval;
  207. }
  208. template<class S, class T, class U, class V> inline void arrInsert(const int k, int &sz, S a[], const S aval, T b[], const T bval, U c[], const U cval, V d[], const V dval){
  209.   int i;
  210.   sz++;
  211.   for(i=sz-1;i>k;i--){
  212.     a[i] = a[i-1];
  213.   }
  214.   for(i=sz-1;i>k;i--){
  215.     b[i] = b[i-1];
  216.   }
  217.   for(i=sz-1;i>k;i--){
  218.     c[i] = c[i-1];
  219.   }
  220.   for(i=sz-1;i>k;i--){
  221.     d[i] = d[i-1];
  222.   }
  223.   a[k] = aval;
  224.   b[k] = bval;
  225.   c[k] = cval;
  226.   d[k] = dval;
  227. }
  228. template<class T, class S> T inline cDiv(T a, S b){
  229.   T m;
  230.   if(b < 0){
  231.     a = -a;
  232.     b = -b;
  233.   }
  234.   m = a % b;
  235.   if(m == 0){
  236.     return a / b;
  237.   }
  238.   if(m < 0){
  239.     m += b;
  240.   }
  241.   return (a + b - m) / b;
  242. }
  243. int N;
  244. long long X[1000];
  245. long long Y[1000];
  246. int sz;
  247. long long dx[1000000];
  248. long long dy[1000000];
  249. long long dp1[1000000];
  250. long long dp2[1000000];
  251. int ls;
  252. long long lss[1000000];
  253. int main(){
  254.   wmem = memarr;
  255.   long long a;
  256.   long long b;
  257.   long long c;
  258.   long long d;
  259.   long long i;
  260.   long long j;
  261.   long long k;
  262.   long long res = 0;
  263.   map<long long,int> s;
  264.   map<pair<long long,long long>,int> ss;
  265.   rd(N);
  266.   {
  267.     int Lj4PdHRW;
  268.     for(Lj4PdHRW=(0);Lj4PdHRW<(N);Lj4PdHRW++){
  269.       rd(X[Lj4PdHRW]);
  270.       rd(Y[Lj4PdHRW]);
  271.     }
  272.   }
  273.   for(i=(0);i<(N);i++){
  274.     for(j=(i+1);j<(N);j++){
  275.       a = X[i] - X[j];
  276.       b = Y[i] - Y[j];
  277.       if(a < 0 || (a == 0 && b < 0)){
  278.         {
  279.           auto xr20shxY = (-1);
  280.           a *= xr20shxY;
  281.           b *= xr20shxY;
  282.         }
  283.       }
  284.       {
  285.         auto t_ynMSdg = (GCD_L(abs(a), abs(b)));
  286.         a /= t_ynMSdg;
  287.         b /= t_ynMSdg;
  288.       }
  289.       {
  290.         auto KrdatlYV = (X[i]);
  291.         auto ao_dF3pO = ( Y[i]);
  292.         c = KrdatlYV;
  293.         d = ao_dF3pO;
  294.       }
  295.       if(a > 0){
  296.         k = cDiv(-c, a);
  297.         {
  298.           auto tU__gIr_ = (k*a);
  299.           auto a2conNHc = ( k*b);
  300.           c += tU__gIr_;
  301.           d += a2conNHc;
  302.         }
  303.       }
  304.       else{
  305.         d = 0;
  306.       }
  307.       arrInsert(sz, sz, dx, a, dy, b, dp1, c, dp2, d);
  308.     }
  309.   }
  310.   sortA_L(sz, dx, dy, dp1, dp2);
  311.   for(i=(0);i<(sz);i++){
  312.     ls = 1;
  313.     lss[0] = 1;
  314.     while(i+1 < sz && dx[i]==dx[i+1] && dy[i]==dy[i+1]){
  315.       if(dp1[i]!=dp1[i+1] || dp2[i]!=dp2[i+1]){
  316.         lss[ls++] = 0;
  317.       }
  318.       lss[ls-1]++;
  319.       i++;
  320.     }
  321.     {
  322.       int jZyWAPpY;
  323.       long long jbtyPBGc;
  324.       if(ls==0){
  325.         jbtyPBGc = 0;
  326.       }
  327.       else{
  328.         jbtyPBGc = lss[0];
  329.         for(jZyWAPpY=(1);jZyWAPpY<(ls);jZyWAPpY++){
  330.           jbtyPBGc += lss[jZyWAPpY];
  331.         }
  332.       }
  333.       k =jbtyPBGc;
  334.     }
  335.     res += k * (k-1) / 2;
  336.     for(j=(0);j<(ls);j++){
  337.       res -= lss[j] * (lss[j]-1) / 2;
  338.     }
  339.   }
  340.   for(i=(0);i<(N);i++){
  341.     for(j=(i+1);j<(N);j++){
  342.       d = (X[i] + X[j]) * (4000000000LL + 5) + (Y[i] + Y[j]);
  343.       a = X[i] - X[j];
  344.       b = Y[i] - Y[j];
  345.       if(a < 0 || (a == 0 && b < 0)){
  346.         {
  347.           auto gEg5UqEA = (-1);
  348.           a *= gEg5UqEA;
  349.           b *= gEg5UqEA;
  350.         }
  351.       }
  352.       {
  353.         auto Hjfu7Vx7 = (GCD_L(abs(a), abs(b)));
  354.         a /= Hjfu7Vx7;
  355.         b /= Hjfu7Vx7;
  356.       }
  357.       c = a * (4000000000LL + 5) + b;
  358.       res -= (s[d]++);
  359.       res += (ss[make_pair(d,c)]++);
  360.     }
  361.   }
  362.   wt_L(res);
  363.   wt_L('\n');
  364.   return 0;
  365. }
  366. // cLay varsion 20201102-1
  367.  
  368. // --- original code ---
  369. // int N;
  370. // ll X[1000], Y[1000];
  371. // 
  372. // int sz; ll dx[1d6], dy[1d6], dp1[1d6], dp2[1d6];
  373. // int ls; ll lss[1d6];
  374. // {
  375. //   ll a, b, c, d, i, j, k;
  376. //   ll res = 0;
  377. //   map<ll,int> s;
  378. //   map<pair<ll,ll>,int> ss;
  379. //   rd(N,(X,Y)(N));
  380. // 
  381. //   rep(i,N) rep(j,i+1,N){
  382. //     a = X[i] - X[j];
  383. //     b = Y[i] - Y[j];
  384. //     if(a < 0 || (a == 0 && b < 0)) (a, b) *= -1;
  385. //     (a, b) /= gcd(abs(a), abs(b));
  386. //     (c, d) = (X[i], Y[i]);
  387. //     if(a > 0){
  388. //       k = cDiv(-c, a);
  389. //       (c, d) += (k*a, k*b);
  390. //     } else {
  391. //       d = 0;
  392. //     }
  393. //     arrInsert(sz, sz, dx, a, dy, b, dp1, c, dp2, d);
  394. //   }
  395. // 
  396. //   sortA(sz, dx, dy, dp1, dp2);
  397. //   rep(i,sz){
  398. //     ls = 1;
  399. //     lss[0] = 1;
  400. //     while(i+1 < sz && dx[i]==dx[i+1] && dy[i]==dy[i+1]){
  401. //       if(dp1[i]!=dp1[i+1] || dp2[i]!=dp2[i+1]) lss[ls++] = 0;
  402. //       lss[ls-1]++;
  403. //       i++;
  404. //     }
  405. //     k = sum(lss(ls));
  406. //     res += k * (k-1) / 2;
  407. //     rep(j,ls) res -= lss[j] * (lss[j]-1) / 2;
  408. //   }
  409. // 
  410. //   rep(i,N) rep(j,i+1,N){
  411. //     d = (X[i] + X[j]) * (4d9 + 5) + (Y[i] + Y[j]);
  412. // 
  413. //     a = X[i] - X[j];
  414. //     b = Y[i] - Y[j];
  415. //     if(a < 0 || (a == 0 && b < 0)) (a, b) *= -1;
  416. //     (a, b) /= gcd(abs(a), abs(b));
  417. //     c = a * (4d9 + 5) + b;
  418. // 
  419. //     res -= (s[d]++);
  420. //     res += (ss[make_pair(d,c)]++);
  421. //   }
  422. //   wt(res);
  423. // }
  424.  
Time limit exceeded #stdin #stdout 5s 4256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/w0vTBW
language:
C++ (gcc 8.3)
created:
3 years ago
visibility:
secret

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!