1

n<=500

法一：随机化最大团

法二：

每个蜘蛛是一个三维直线(x,y,t)

考虑按照所属面分别考虑这些蜘蛛

一些个蜘蛛相交，当且仅当这些直线共面

还有一种蜘蛛交在一点的情况，先判掉：

枚举两个直线，确定平面

枚举剩下的直线，考虑是否有交点

先考虑是否有所有直线交在一点

然后平行的只保留一个

再考虑共面

如果之前有三直线不共点：直接查是不是在平面上

否则如果和第一第二条直线交点重合，先留着，最后和某一个交点不重合的进行判断是否共面

 

2

给出一个点集

• 你要选择一个子集，其中每个点有 pi 的概率在子集中

• 求凸包面积的期望

? ≤ 10^3

凸包的面积计算可以独立

考虑每个边在所有凸包上出现的贡献

带方向枚举每条边，这条边存在当且仅当右侧没有点并且两个端点存在

每次级角排序+扫描线即可

 

3

你有 ? 个点

• 求最多能选出多少个其中的点，使得这些点两两之间的连线不和

以原点为圆心 ? 为半径的圆相交

? ≤ 2000

其实，就是这些点和圆的两个切线之间的圆弧有关系，设圆弧为si

则这个集合的两两圆弧必须相交并且不互相包含

枚举第一个圆弧是哪个，剩下可选择的圆弧按照左端点排序，右端点必然是上升的，所以对右端点求LIS即可

挺巧的

 

4

平面上有很多蓝点和红点

你需要求一个最大的蓝点为顶点的凸多边形，要求其边界和内部都不能

出现红点

n<=100

bzoj3778共鸣

类似THUWC2019 D2T3

考虑枚举左下角，f[i][j]最后一个是j，倒数第二个是i，O(n^3)

发现枚举下一个的时候，就是多了一个三角形，所以预处理这个三角形内部有没有红点即可

预处理方法：

法一：O(n^3)

把三个角内部的红色点都加上，黑色是该区域红点计算次数

这个可以预处理以每个点的级角序排序结果+双指针：O(n^3)预处理

每个线段箭头方向的红点数量也加上

然后减去所有红点个数的2倍

就是最后的答案了！

 

法二：不完全O(n^4)

枚举右下角的点s，把涉及到的点放进数组

级角序排序

顺序枚举两个点i，j和s形成三角形，同时用指针维护可能出现在三角形的红点编号区间[be+1，ptr]

暴力在这个区间看是否有红点在三角形中

只要随便判断叉积是否为负什么的即可

#include
      
       #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
       
        using namespace std;typedef long long ll;template
        
         il void rd(T &x){    char ch;x=0;bool fl=false;while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);(fl==true)&&(x=-x);}template
         
          il void output(T x){
    if(x/10)output(x/10);putchar(x%10+'0');}template
          
           il void ot(T x){
    if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
           
            il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Modulo{const int mod=998244353;int ad(int x,int y){ return (x+y)>=mod?x+y-mod:x+y;}void inc(int &x,int y){x=ad(x,y);}int mul(int x,int y){ return (ll)x*y%mod;}void inc2(int &x,int y){x=mul(x,y);}int qm(int x,int y=mod-2){ int ret=1;while(y){ if(y&1) ret=mul(x,ret);x=mul(x,x);y>>=1;}return ret;}}//using namespace Modulo;namespace Miracle{const int N=105;const int inf=0x3f3f3f3f;int n,m;struct po{ int x,y; po(){} po(int xx,int yy){x=xx;y=yy;} po friend operator +(po a,po b){ return po(a.x+b.x,a.y+b.y); } po friend operator -(po a,po b){ return po(a.x-b.x,a.y-b.y); } int friend operator *(po a,po b){ return a.x*b.y-a.y*b.x; }}a[N],b[N],st[N],no[N],std;int ca,cb;bool smal(po a,po b){ return atan2(a.y-std.y,a.x-std.x)
            
             std.x||(a[i].x==std.x&&a[i].y>=std.y)) st[++ca]=a[i]; } for(reg i=1;i<=m;++i){ if(b[i].x>std.x||(b[i].x==std.x&&b[i].y>=std.y)) no[++cb]=b[i]; } sort(st+1,st+ca+1,cmp);sort(no+1,no+cb+1,cmp); for(reg i=1;i<=ca;++i){ int be=0; while(be
             
              =0){ ok[i][j]=-1; } } } } memset(f,-inf,sizeof f); for(reg i=1;i<=ca;++i){ for(reg j=i+1;j<=ca;++j){ if(ok[i][j]!=-1){ f[i][j]=max(f[i][j],(st[i]-std)*(st[j]-std)); } for(reg k=j+1;k<=ca;++k){ if(ok[j][k]!=-1&&(st[j]-st[i])*(st[k]-st[i])>=0){ f[j][k]=max(f[j][k],f[i][j]+(st[j]-std)*(st[k]-std)); } } ans=max(ans,f[i][j]); } }}int main(){ rd(n);rd(m); for(reg i=1;i<=n;++i) rd(a[i].x),rd(a[i].y); for(reg i=1;i<=m;++i) rd(b[i].x),rd(b[i].y); for(reg i=1;i<=n;++i){ std=a[i]; sol(i); } printf("%.2lf",(double)ans/2.0); return 0;}}signed main(){ Miracle::main(); return 0;}/* Author: *Miracle**/
             
            
           
          
         
        
       
      

 

5

平面上有 ? 个圆

你需要从一个起点到一个终点

每次，如果你在其中一个圆内，你可以把自己绕圆心旋转一个角度

问能不能在有限步内走到

n<=50

求交点，暴力BFS

 

6

给一个格点凸多边形，两个人轮流操作

每次操作需要画一个格点凸多边形（面积不能是 0），满足该多

边形的顶点在上一个多边形的内部或边界上，但不能和上一个多

边形的顶点重合

求是先手必胜还是后手必胜

? ≤ 100, |?|, |?| ≤ 10^5

伪博弈题

只要凸多边形内部有一个三角形，那么先手就必胜了

枚举横坐标，考虑这个横坐标这一列有多少个点（枚举n个外边界，卡出边界即可）

如果存在>=2个有点，存在一个>=2个，先手必胜

否则一定都共线，先手必败