这个题半平面交很显然了，都直接给出直线了有木有！！？？答案就是交出来的（分段函数）凸壳有几块就行。。有相等什么的情况特别恶心。
然而本蒟蒻直接上的模板还是错了。。。跪（不知道为什么）
1 /*#include<bits/stdc++.h> 2 #define N 100005 3 #define LL long long 4 #define eps 1e-8 5 #define double long double 6 using namespace std; 7 inline int ra() 8 { 9 int x=0,f=1; char ch=getchar(); 10 while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();} 11 while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} 12 return x*f; 13 } 14 const double inf=1e15; 15 int n,cnt,tot,L,R,ans[N],num,orz; 16 struct data_in{int k,b; int id;}q[N]; 17 struct point{double x,y;}; 18 struct line{ 19 point a,b; double angle; int id; 20 void print(){ 21 printf("%.1lf %.1lf %.1lf %.1lf ",a.x,a.y,b.x,b.y); 22 } 23 }l[N],s[N]; 24 double operator * (point a, point b){ 25 return a.x*b.y-a.y*b.x; 26 } 27 point operator - (point a, point b){ 28 point t; t.x=a.x-b.x; t.y=a.y-b.y; return t; 29 } 30 bool operator < (line a, line b){ 31 if (a.angle==b.angle) return (b.b-a.a)*(a.b-a.a)>=0; 32 return a.angle<b.angle; 33 } 34 bool operator == (point a, point b){ 35 return a.x==b.x && a.y==b.y; 36 } 37 point intersection(line a, line b) 38 { 39 point ans; double k1,k2,t; 40 k1=(b.a-a.a)*(a.b-a.a); 41 k2=(a.b-a.a)*(b.b-a.a); 42 t=k1/(k1+k2); 43 ans.x=b.a.x+(b.b.x-b.a.x)*t; 44 ans.y=b.a.y+(b.b.y-b.a.y)*t; 45 return ans; 46 } 47 bool jud(line a, line b, line t) 48 { 49 point p=intersection(a,b); 50 // printf("%lf %lf",p.x,p.y);while(1); 51 return (t.a-p)*(t.b-p)<0; 52 } 53 void half_plane_intersection() 54 { 55 for (int i=1; i<=cnt; i++) 56 if ((l[i].angle!=l[i-1].angle) || (l[i].angle==l[i-1].angle && l[i].a==l[i-1].a && l[i].b==l[i-1].b)) l[++tot]=l[i]; 57 // for (int i=1; i<=tot; i++) l[i].print(); 58 L=1; R=0; s[++R]=l[1]; s[++R]=l[2]; 59 // cout<<jud(l[1],l[2],l[3]); 60 for (int i=3; i<=tot; i++) 61 { 62 if (l[i].a==l[i-1].a && l[i].b==l[i-1].b) {s[++R]=l[i]; continue;} 63 while (L<R && jud(s[R],s[R-1],l[i])) R--; 64 while (L<R && jud(s[L],s[L+1],l[i])) L++; 65 s[++R]=l[i]; 66 } 67 while (L<R && jud(s[R],s[R-1],s[L])) R--; 68 while (L<R && jud(s[L],s[L+1],s[R])) L++; 69 } 70 bool cmp(data_in a, data_in b) 71 { 72 if (a.k==b.k) return a.b<b.b; 73 return a.k<b.k; 74 } 75 int main() 76 { 77 n=ra(); 78 for (int i=1; i<=n; i++) q[i].b=ra(); 79 for (int i=1; i<=n; i++) q[i].k=ra(); 80 for (int i=1; i<=n; i++) q[i].id=i; 81 sort(q+1,q+n+1,cmp); 82 for (int i=1; i<=n; i++) 83 if (q[i].k!=q[i-1].k || (q[i].k==q[i-1].k && q[i].b==q[i-1].b)) q[++orz]=q[i]; 84 for (int i=1; i<=orz; i++) 85 { 86 l[++cnt].a.x=0; l[cnt].a.y=q[i].b; 87 l[cnt].b.x=2; l[cnt].b.y=2*q[i].k+q[i].b; 88 l[cnt].id=q[i].id; 89 } 90 l[++cnt].a.x=-1; l[cnt].a.y=inf; l[cnt].b.x=-1; l[cnt].b.y=-1; 91 l[++cnt].a.x=-1; l[cnt].a.y=-1; l[cnt].b.x=inf; l[cnt].b.y=-1; 92 for (int i=1; i<=cnt; i++) 93 l[i].angle=atan2(l[i].b.y-l[i].a.y,l[i].b.x-l[i].a.x); 94 sort(l+1,l+cnt+1); 95 half_plane_intersection(); 96 for (int i=L; i<=R; i++) 97 if (s[i].id) ans[++num]=s[i].id; 98 sort(ans+1,ans+num+1); 99 cout<<num<<endl; 100 for (int i=1; i<=num; i++) 101 { 102 printf("%d",ans[i]); 103 if (i!=num) printf(" "); 104 } 105 return 0; 106 }*/ 107 108 #include<cstdio> 109 #include<algorithm> 110 #define N 100005 111 #define eps 1e-8 112 using namespace std; 113 int n,top; 114 int ans[N]; 115 struct line{ 116 int k,b,id; 117 friend bool operator < (line a, line b){ 118 if (a.k==b.k) return a.b<b.b; 119 return a.k<b.k; 120 } 121 friend double inter(line a, line b){ 122 return (double)(a.b-b.b)/(b.k-a.k); 123 } 124 }c[N],q[N]; 125 bool jud(line a, line b, line t) 126 { 127 return inter(a,b)>inter(a,t); 128 } 129 int main() 130 { 131 scanf("%d",&n); 132 for (int i=1; i<=n; i++) scanf("%d",&c[i].b); 133 for (int i=1; i<=n; i++) scanf("%d",&c[i].k); 134 for (int i=1; i<=n; i++) c[i].id=i; 135 sort(c+1,c+n+1); top=1; 136 for (int i=2; i<=n; i++) 137 { 138 if (c[i].k!=c[i-1].k || (c[i].k==c[i-1].k && c[i].b==c[i-1].b)) 139 top++; 140 c[top]=c[i]; 141 } 142 n=top; top=0; 143 q[++top]=c[1]; ans[1]=c[1].id; 144 for (int i=2; i<=n; i++) 145 { 146 while (top>=1 && inter(q[top],c[i])<-eps) top--; 147 while (top>=2 && jud(q[top-1],q[top],c[i])) top--; 148 q[++top]=c[i]; ans[top]=c[i].id; 149 } 150 printf("%d ",top); 151 sort(ans+1,ans+top+1); 152 for (int i=1; i<=top; i++) 153 { 154 printf("%d",ans[i]); 155 if (i!=top) printf(" "); 156 } 157 // while (1); 158 return 0; 159 }