Advertisement
yicongli

LG3256

Mar 1st, 2019
47
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.97 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7.  
  8. template<typename T>
  9. inline void read(T&x){
  10.     x=0;T k=1;char gc;
  11.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  12.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  13. }
  14.  
  15. #define db long double
  16.  
  17. const db INF=2e9+1;
  18. const int N=10000+7;
  19.  
  20. inline db sqr(db x){
  21.     return x*x;
  22. }
  23.  
  24. struct Point{
  25.     db x,y;
  26.    
  27.     inline Point(){}
  28.     inline Point(db _x,db _y):x(_x),y(_y){}
  29.    
  30. };
  31.  
  32. #define Vec Point
  33.  
  34. inline Vec operator +(const Vec &a,const Vec &b){
  35.     return Vec(a.x+b.x,a.y+b.y);
  36. }
  37.  
  38. inline Vec operator -(const Vec &a,const Vec &b){
  39.     return Vec(a.x-b.x,a.y-b.y);
  40. }
  41.  
  42. inline void operator +=(Vec &a,const Vec &b){
  43.     a.x+=b.x,a.y+=b.y;
  44. }
  45.  
  46. inline void operator -=(Vec &a,const Vec &b){
  47.     a.x-=b.x,a.y-=b.y;
  48. }
  49.  
  50. inline Vec operator *(const Vec &a,const db &b){
  51.     return Vec(a.x*b,a.y*b);
  52. }
  53.  
  54. inline Vec operator /(const Vec &a,const db &b){
  55.     return Vec(a.x/b,a.y/b);
  56. }
  57.  
  58. inline db Cross(const Vec &a,const Vec &b){
  59.     return a.x*b.y-a.y*b.x;
  60. }
  61.  
  62. inline db Angle(const Vec &a){
  63.     return atan2(a.y,a.x);
  64. }
  65.  
  66. struct Line{
  67.     Point S,T;
  68.     db theta;
  69.     int id;
  70.    
  71.     inline Line(){}
  72.     inline Line(const Point &A,const Point &B,int x=0):S(A),T(B),theta(Angle(B-A)),id(x){}
  73.    
  74. };
  75.  
  76. #define Seg Line
  77.  
  78. inline bool operator < (const Line &A,const Line &B){
  79.     if(A.theta-B.theta!=0)return A.theta<B.theta;
  80.     return Cross(A.T-A.S,B.S-A.S)<0;
  81. }
  82.  
  83. inline Point LineCross(const Line &a,const Line &b){
  84.     Vec u=a.T-a.S;
  85.     Vec v=b.T-b.S;
  86.     Vec w=a.S-b.S;
  87.     db t=Cross(v,w)/Cross(u,v);
  88.     return a.S+u*t;
  89. }
  90. //on the right or not
  91. inline bool Direction(const Line &a,const Point &A){
  92.     return Cross(a.T-a.S,A-a.S)<0;
  93. }
  94.  
  95. int Q[N];
  96. int head,tail;
  97. bool vis[N];
  98.  
  99. int a[N];
  100. int v[N];
  101. int fa[N];
  102.  
  103. int find(int x){
  104.     return fa[x]==x?x:fa[x]=find(fa[x]);
  105. }
  106.  
  107. inline void uni(int x,int y){
  108.     x=find(x),y=find(y),fa[x]=y;
  109. }
  110.  
  111. inline void Half(Line *A,int n){
  112.     sort(A+1,A+n+1);
  113.     Q[0]=1;
  114.     for(int i=2;i<=n;++i){
  115.         if(A[i].theta==A[i-1].theta){
  116.             if(a[A[i].id]==a[A[i-1].id]){
  117.                 uni(A[i].id,A[i-1].id);
  118.             }
  119.             continue;
  120.         }
  121.         while(head<tail&&Direction(A[i],LineCross(A[Q[tail]],A[Q[tail-1]])))--tail;
  122.         while(head<tail&&Direction(A[i],LineCross(A[Q[head]],A[Q[head+1]])))++head;
  123.         Q[++tail]=i;
  124.     }
  125.     while(head<tail&&Direction(A[Q[head]],LineCross(A[Q[tail]],A[Q[tail-1]])))--tail;
  126.     while(head<tail&&Direction(A[Q[tail]],LineCross(A[Q[head]],A[Q[head+1]])))++head;
  127.     for(int i=head;i<=tail;++i){
  128.         vis[find(A[Q[i]].id)]=1;
  129.     }
  130. }
  131.  
  132. Line A[N];
  133.  
  134. int main(){
  135.     int n;r(n);
  136.     for(int i=1;i<=n;++i)r(a[i]);
  137.     for(int i=1;i<=n;++i)r(v[i]);
  138.     for(int i=1;i<=n;++i)fa[i]=i;
  139.     for(int i=1;i<=n;++i)A[i]=Line(Point(0,a[i]),Point(1,a[i]+v[i]),i);
  140.     A[n+1]=Line(Point(0,INF),Point(0,0));
  141.     A[n+2]=Line(Point(0,0),Point(INF,0));
  142.     Half(A,n+2);
  143.     int cnt=0;
  144.     for(int i=1;i<=n;++i){
  145.         if(vis[find(i)]){
  146.             ++cnt;
  147.         }
  148.     }
  149.     printf("%d\n",cnt);
  150.     for(int i=1;i<=n;++i){
  151.         if(vis[find(i)]){
  152.             printf("%d ",i);
  153.         }
  154.     }
  155.     return 0;
  156. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement