没人做计算几何了，怎么会事呢...
这几把军训...laji时间找点laji题来做
一. 板子
1.basic
2.凸包
3.半平面交
二.板题
三.题目
P3194
给出\(N<50000\)条直线，找出从y正无穷大可见直线
手玩发现所有可见线段构成一个下凸壳。将所有直线按照斜率递增排序，用单调栈维护。栈顶为AB，插入C时，若AC交点在AB交点左侧或重合，则B无贡献。注意每种斜率的直线保留最上面的
for(int i=1;i<=n;++i) {
if(l[i].k==l[i-1].k) continue;
while(cnt>=2) {
point A1=point(1,f(l[stk[cnt]],1)),A2=point(2,f(l[stk[cnt]],2));
point B1=point(1,f(l[stk[cnt-1]],1)),B2=point(2,f(l[stk[cnt-1]],2));
point C1=point(1,f(l[i],1)),C2=point(2,f(l[i],2));
if(dcmp(LL(A1,A2,B1,B2).x-LL(C1,C2,A1,A2).x)>=0) {
cnt--;
} else break;
}
stk[++cnt]=i;
}
P2924
给出\(N<=250\)个点，保证不存在三点共线，求可以由这些点围成的凸包中，最多的点数
dp。注意到转移的斜率是单调的，把n方条边全部连上并按斜率排序作为转移。以每个点为起点dp一次，一定有一个点是转移首尾相连的位置。从起点扩张的正向边与回到起点的反向边的枚举顺序是相反的，不会造成影响
for(int i=1;i<=n;++i) {
memset(f,-0x3f,sizeof(f));
f[i]=0;
for(int j=1;j<=cnt;++j) {
f[e[j].r]=max(f[e[j].r],f[e[j].l]+1);
}
ans=max(ans,f[i]);
}