fork download
  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
stdin
Standard input is empty
stdout
1 0