fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define x first
  4. #define y second
  5. #define sd(n) scanf("%d",&n)
  6. using namespace std;
  7.  
  8. typedef long long LL;
  9. typedef pair<int,int> PII;
  10.  
  11. #define MAXN 100000
  12. #define EPS 1e-9
  13. PII ar[2*MAXN];
  14.  
  15. // * Line intersection
  16. // * Returns the point of intersection of two lines:
  17. // * (x[0],y[0])-(x[1],y[1]) and (x[2],y[2])-(x[3],y[3]). Puts the result (x, y) into (r[0], r[1])
  18. //   and returns true. If there is no intersection, return false.
  19. bool lineIntersect( vector<double>& x, vector<double>& y, vector<double>& r ){
  20.     double n[2]; n[0] = y[3] - y[2]; n[1] = x[2] - x[3];
  21.     double denom = n[0] * ( x[1] - x[0] ) + n[1] * ( y[1] - y[0] );
  22.     if( fabs( denom ) < EPS ) return false;
  23.     double num = n[0] * ( x[0] - x[2] ) + n[1] * ( y[0] - y[2] );
  24.     double t = -num / denom;
  25.     r[0] = x[0] + t * ( x[1] - x[0] );
  26.     r[1] = y[0] + t * ( y[1] - y[0] );
  27.     return true;
  28. }
  29.  
  30.  
  31. //check if region of edge (mid, mid+1) exceeds k
  32. //find interesection of lines (mid, mid+1) and (idx, idx+1)
  33. //use distance to check if valid or not
  34. int f(int mid, int idx, int k){
  35.     vector<double> x(4),y(4),r(2);
  36.     x[0]=ar[mid].x; x[1]=ar[mid+1].x;
  37.     y[0]=ar[mid].y; y[1]=ar[mid+1].y;
  38.     x[2]=ar[idx].x; x[3]=ar[idx+1].x;
  39.     y[2]=ar[idx].y; y[3]=ar[idx+1].y;
  40.  
  41.     if(not lineIntersect(x, y, r))return true;
  42.  
  43.     double dist1=sqrt((r[0]-ar[idx].x)*(r[0]-ar[idx].x) 
  44.             + (r[1]-ar[idx].y)*(r[1]-ar[idx].y));
  45.     double dist2=sqrt((r[0]-ar[idx+1].x)*(r[0]-ar[idx+1].x) 
  46.             + (r[1]-ar[idx+1].y)*(r[1]-ar[idx+1].y));
  47.     if(fabs(dist1-k) < EPS)return 2;
  48.     if(dist1 < dist2 or dist1 + EPS > k)
  49.         return 1;
  50.     return 0;
  51. }
  52.  
  53. int main()
  54. {
  55.     int n,q;
  56.     sd(n),sd(q);
  57.     for(int i=0; i<n; i++)
  58.         sd(ar[i].x),sd(ar[i].y);
  59.     for(int i=n; i<2*n; i++)
  60.         ar[i]=ar[i-n];
  61.     while(q--){
  62.         int idx,k;
  63.         sd(idx),sd(k);
  64.  
  65.         //binary search on edge
  66.         int l=idx, r=l+n, mid;
  67.         while(r-l>1){
  68.             mid=(l+r)/2;
  69.             if(f(mid, idx, k) >= 1)
  70.                 r=mid;
  71.             else l=mid;
  72.         }
  73.  
  74.         if(f((l+1)%n, idx, k) == 2)
  75.             printf("%d %d\n",(l+1)%n, (l+2)%n);
  76.         else
  77.             printf("%d\n", (l+1)%n);
  78.     }
  79.     return 0;
  80. }
Runtime error #stdin #stdout 0s 4972KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/w6DGKA
language:
C++14 (gcc 8.3)
created:
8 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!