Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define gc c=getchar()
- #define r(x) read(x)
- template<typename T>
- inline void read(T&x){
- x=0;T k=1;char gc;
- while(!isdigit(c)){if(c=='-')k=-1;gc;}
- while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
- }
- #define db long double
- const db INF=2e9+1;
- const int N=10000+7;
- inline db sqr(db x){
- return x*x;
- }
- struct Point{
- db x,y;
- inline Point(){}
- inline Point(db _x,db _y):x(_x),y(_y){}
- };
- #define Vec Point
- inline Vec operator +(const Vec &a,const Vec &b){
- return Vec(a.x+b.x,a.y+b.y);
- }
- inline Vec operator -(const Vec &a,const Vec &b){
- return Vec(a.x-b.x,a.y-b.y);
- }
- inline void operator +=(Vec &a,const Vec &b){
- a.x+=b.x,a.y+=b.y;
- }
- inline void operator -=(Vec &a,const Vec &b){
- a.x-=b.x,a.y-=b.y;
- }
- inline Vec operator *(const Vec &a,const db &b){
- return Vec(a.x*b,a.y*b);
- }
- inline Vec operator /(const Vec &a,const db &b){
- return Vec(a.x/b,a.y/b);
- }
- inline db Cross(const Vec &a,const Vec &b){
- return a.x*b.y-a.y*b.x;
- }
- inline db Angle(const Vec &a){
- return atan2(a.y,a.x);
- }
- struct Line{
- Point S,T;
- db theta;
- int id;
- inline Line(){}
- inline Line(const Point &A,const Point &B,int x=0):S(A),T(B),theta(Angle(B-A)),id(x){}
- };
- #define Seg Line
- inline bool operator < (const Line &A,const Line &B){
- if(A.theta-B.theta!=0)return A.theta<B.theta;
- return Cross(A.T-A.S,B.S-A.S)<0;
- }
- inline Point LineCross(const Line &a,const Line &b){
- Vec u=a.T-a.S;
- Vec v=b.T-b.S;
- Vec w=a.S-b.S;
- db t=Cross(v,w)/Cross(u,v);
- return a.S+u*t;
- }
- //on the right or not
- inline bool Direction(const Line &a,const Point &A){
- return Cross(a.T-a.S,A-a.S)<0;
- }
- int Q[N];
- int head,tail;
- bool vis[N];
- int a[N];
- int v[N];
- int fa[N];
- int find(int x){
- return fa[x]==x?x:fa[x]=find(fa[x]);
- }
- inline void uni(int x,int y){
- x=find(x),y=find(y),fa[x]=y;
- }
- inline void Half(Line *A,int n){
- sort(A+1,A+n+1);
- Q[0]=1;
- for(int i=2;i<=n;++i){
- if(A[i].theta==A[i-1].theta){
- if(a[A[i].id]==a[A[i-1].id]){
- uni(A[i].id,A[i-1].id);
- }
- continue;
- }
- while(head<tail&&Direction(A[i],LineCross(A[Q[tail]],A[Q[tail-1]])))--tail;
- while(head<tail&&Direction(A[i],LineCross(A[Q[head]],A[Q[head+1]])))++head;
- Q[++tail]=i;
- }
- while(head<tail&&Direction(A[Q[head]],LineCross(A[Q[tail]],A[Q[tail-1]])))--tail;
- while(head<tail&&Direction(A[Q[tail]],LineCross(A[Q[head]],A[Q[head+1]])))++head;
- for(int i=head;i<=tail;++i){
- vis[find(A[Q[i]].id)]=1;
- }
- }
- Line A[N];
- int main(){
- int n;r(n);
- for(int i=1;i<=n;++i)r(a[i]);
- for(int i=1;i<=n;++i)r(v[i]);
- for(int i=1;i<=n;++i)fa[i]=i;
- for(int i=1;i<=n;++i)A[i]=Line(Point(0,a[i]),Point(1,a[i]+v[i]),i);
- A[n+1]=Line(Point(0,INF),Point(0,0));
- A[n+2]=Line(Point(0,0),Point(INF,0));
- Half(A,n+2);
- int cnt=0;
- for(int i=1;i<=n;++i){
- if(vis[find(i)]){
- ++cnt;
- }
- }
- printf("%d\n",cnt);
- for(int i=1;i<=n;++i){
- if(vis[find(i)]){
- printf("%d ",i);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement