fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. const int nmax=10005;
  5. const int vmax=10;
  6.  
  7. int n, x[nmax], y[nmax], q, xo, yo, vxo, vyo, ax, bx, ay, by, avx, bvx, avy, bvy;
  8. pair<int,int> cl[2*vmax+1][2*vmax+1][nmax];
  9. int pos, ans;
  10.  
  11. void QSort(int L, int R, pair<int,int> A[]);
  12. int Left(int u, int v, int e);
  13. int Right(int u, int v, int e);
  14. int Less(int u, int v, int L, int R, int val);
  15. int More(int u, int v, int L, int R, int val);
  16.  
  17.  
  18. int main()
  19. {
  20.   scanf("%d\n",&n);
  21.   for(int i=1;i<=n;i++) scanf("%d %d\n",&x[i],&y[i]);
  22.  
  23.   for(int i=0;i<=2*vmax;i++)
  24.     for(int j=0;j<=2*vmax;j++)
  25.     {
  26.         for(int k=1;k<=n;k++)
  27.         {
  28.             cl[i][j][k].first=x[k]*(j-vmax)-y[k]*(i-vmax);
  29.             cl[i][j][k].second= j==vmax ? x[k]:y[k];
  30.         }
  31.         QSort(1, n, cl[i][j]);
  32.     }
  33.  
  34.   scanf("%d\n",&q);
  35.   scanf("%d %d %d %d\n",&xo, &yo, &vxo, &vyo);
  36.   scanf("%d %d %d %d %d %d %d %d\n",&ax, &bx, &ay, &by, &avx, &bvx, &avy, &bvy);
  37.  
  38.   ax=ax % 20001;
  39.   bx=bx % 20001;
  40.   ay=ay % 20001;
  41.   by=by % 20001;
  42.   avx=avx % 21;
  43.   bvx=bvx % 21;
  44.   avy=avy % 21;
  45.   bvy=bvy % 21;
  46.  
  47.   pos=1, ans=0;
  48.  
  49.   for(int t=1;t<=q;t++)
  50.   {
  51.     if(t>1)
  52.     {
  53.       xo= xo % 20001;
  54.       if(xo<0) xo+=20001;
  55.       yo= yo % 20001;
  56.       if(yo<0) yo+=20001;
  57.       bx= bx % 20001;
  58.       if(bx<0) bx+=20001;
  59.       by= by % 20001;
  60.       if(by<0) by+=20001;
  61.  
  62.       xo=(ax*(xo+10000)+bx) % 20001 - 10000;
  63.       yo=(ay*(yo+10000)+by) % 20001 - 10000;
  64.       vxo=(avx*(vxo+10)+bvx) % 21 - 10;
  65.       vyo=(avy*(vyo+10)+bvy) % 21 - 10;
  66.     }
  67.     int i=vxo+vmax, j=vyo+vmax;
  68.     int e=xo*vyo-yo*vxo;
  69.     int alpha=Left(i, j, e), beta=Right(i, j, e);
  70.     if(alpha==-1) continue;
  71.     int now=0, ind;
  72.     if(vyo==0)
  73.     {
  74.       if(vxo>0)
  75.       {
  76.         ind=More(i,j,alpha,beta,xo);
  77.         if(ind!=-1) now=beta-ind+1;
  78.       }
  79.       else
  80.       {
  81.         ind=Less(i,j,alpha,beta,xo);
  82.         if(ind!=-1) now=ind-alpha+1;
  83.       }
  84.     }
  85.     else
  86.     {
  87.       if(vyo>0)
  88.       {
  89.         ind=More(i,j,alpha,beta,yo);
  90.         if(ind!=-1) now=beta-ind+1;
  91.       }
  92.       else
  93.       {
  94.         ind=Less(i,j,alpha,beta,yo);
  95.         if(ind!=-1) now=ind-alpha+1;
  96.       }
  97.     }
  98.     if(now>=ans) ans=now, pos=t;
  99.   }
  100.  
  101.   printf("%d %d",pos, ans);
  102.  
  103.   return 0;
  104. }
  105.  
  106.  
  107.  
  108.  
  109. void QSort(int L, int R, pair<int,int> A[])
  110. {
  111.   pair<int,int> X=A[(L+R)/2], Y;
  112.   int i=L, j=R;
  113.   while(i<=j)
  114.   {
  115.     while(A[i].first<X.first || A[i].first==X.first && A[i].second<X.second) i++;
  116.     while(A[j].first>X.first || A[j].first==X.first && A[j].second>X.second) j--;
  117.     if(i<=j)
  118.     {
  119.       Y=A[i], A[i]=A[j], A[j]=Y;
  120.       i++, j--;
  121.     }
  122.   }
  123.   if(L<j) QSort(L, j, A);
  124.   if(i<R) QSort(i, R, A);
  125. }
  126.  
  127.  
  128. int Left(int u, int v, int e)
  129. {
  130.   int L=1, R=n, mid;
  131.   while(R-L>1)
  132.   {
  133.     mid=(L+R)/2;
  134.     if(cl[u][v][mid].first<e) L=mid;
  135.     else R=mid;
  136.   }
  137.   if(cl[u][v][L].first==e) return L;
  138.   if(cl[u][v][R].first==e) return R;
  139.   return -1;
  140. }
  141.  
  142.  
  143. int Right(int u, int v, int e)
  144. {
  145.   int L=1, R=n, mid;
  146.   while(R-L>1)
  147.   {
  148.     mid=(L+R)/2;
  149.     if(cl[u][v][mid].first<=e) L=mid;
  150.     else R=mid;
  151.   }
  152.   if(cl[u][v][R].first==e) return R;
  153.   if(cl[u][v][L].first==e) return L;
  154.   return -1;
  155. }
  156.  
  157.  
  158.  
  159. int Less(int u, int v, int L, int R, int val)
  160. {
  161.   int mid;
  162.   while(R-L>1)
  163.   {
  164.     mid=(L+R)/2;
  165.     if(cl[u][v][mid].second<=val) L=mid;
  166.     else R=mid;
  167.   }
  168.   if(cl[u][v][R].second<=val) return R; 
  169.   if(cl[u][v][L].second<=val) return L;
  170.   return -1;
  171. }
  172.  
  173.  
  174. int More(int u, int v, int L, int R, int val)
  175. {
  176.   int mid;
  177.   while(R-L>1)
  178.   {
  179.     mid=(L+R)/2;
  180.     if(cl[u][v][mid].second>=val) R=mid;
  181.     else L=mid;
  182.   }
  183.   if(cl[u][v][L].second>=val) return L; 
  184.   if(cl[u][v][R].second>=val) return R;
  185.   return -1;
  186. }
Success #stdin #stdout 0s 4316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 0
https://ideone.com/0Fm1CG
language:
C++14 (gcc 8.3)
created:
5 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!