非常带劲之计算几何
写的头晕= =
就是平面图转对偶图然后最小割
由于p非常小我们枚举所有保护状态然后割一下
建图真的烦 就是把区域划分出来看一下每一个古迹点是否被小区域包含【好像也可以写点定位】
然后我好像判左右叉积又双叒叕的写反了？
整个画出图来然后发现好像没建错图= = 然后把!删掉竟然过了= =于是愉快改成onright= =
区域划分就是双向直线然后每次找反向的极角的最近的就可以了 可以画个图大概就是这个样子
红的就是反向边 找的就是蓝色的 找一圈就一定会找回来
然后别忘了记录那个外边的无限平面
写起来带劲2333
//Love and Freedom.
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<vector>
#define inf 20021225
#define ll long long
#define db double
#define eps 1e-8
using namespace std;
#define mxm 200000
#define mxn 1100
struct poi
{
db x,y;
poi(){}
poi(db _x,db _y){x=_x,y=_y;}
};
typedef poi vec;
vec operator +(vec a,vec b){return vec(a.x+b.x,a.y+b.y);}
vec operator -(vec a,vec b){return vec(a.x-b.x,a.y-b.y);}
vec operator *(vec a,db b){return vec(a.x*b,a.y*b);}
db cross(vec a,vec b){return a.x*b.y-a.y*b.x;}
db value(vec a){return a.x*a.x-a.y*a.y;}
db len(vec a){return sqrt(a.x*a.x+a.y*a.y);}
struct line
{
poi p; vec v; db ang;
int x,y,w,another,flag;
line(){}
line(poi _p,vec _v){p=_p,v=_v,ang=atan2(v.y,v.x);flag=0;}
};
bool onright(poi p,line l){return cross(l.p+l.v-p,l.p-p)>0;}
vector<int> e[mxn];
poi spc[mxn],stk[mxn];
bool v[mxn],out[mxn];
int n,m,p,bel[mxn];
line li[mxm];
bool cmp(int a,int b)
{
return li[a].ang<li[b].ang||abs(li[a].ang-li[b].ang)<eps&&cross(li[a].v,li[b].v)>0;
}
void find(int tmp,int id)
{
memset(v,true,sizeof(v));
for(int i=1;i<=p;i++)
if(v[i]) v[i]=onright(spc[i],li[tmp]);
int start = li[tmp].x, now = li[tmp].y; li[tmp].flag=id;
db area = cross(stk[start],stk[now]);
do
{
vector<int>::iterator it = upper_bound(e[now].begin(),e[now].end(),li[tmp].another,cmp);
if(it==e[now].end()) it=e[now].begin();
//if(id==1) printf("===%d %lf %lf===\n",now,li[li[tmp].another].ang,li[*it].ang);
tmp =*it; now=li[tmp].y;
li[tmp].flag = id; area += cross(stk[li[tmp].x],stk[li[tmp].y]);
for(int i=1;i<=p;i++) if(v[i]) v[i]=onright(spc[i],li[tmp]);
}while(start!=now);
for(int i=1;i<=p;i++) if(v[i]) bel[i]=id;
if(area>0) out[id]=1;
}
int ed,blk;
struct Edge
{
int x,y,w;
Edge(){}
Edge(int _x,int _y,int _w){x=_x,y=_y,w=_w;}
}E[mxm];
int Ecnt;
int ans[mxn];
struct edge{int to,lt,f;};
struct maxflow
{
edge e[mxm];
int in[mxn],cnt=1,dis[mxn],s,t;
queue<int> que;
void init()
{
s=mxn-10; t=s+1; cnt=1;
memset(in,0,sizeof(in));
}
void add(int x,int y,int f)
{
e[++cnt].to=y;e[cnt].lt=in[x];e[cnt].f=f;in[x]=cnt;
e[++cnt].to=x;e[cnt].lt=in[y];e[cnt].f=0;in[y]=cnt;
}
bool bfs()
{
memset(dis,0,sizeof(dis));
while(!que.empty()) que.pop();
dis[s]=1; que.push(s);
while(!que.empty())
{
int x=que.front(); que.pop();
for(int i=in[x];i;i=e[i].lt)
{
int y=e[i].to;
if(!dis[y]&&e[i].f)
dis[y]=dis[x]+1,que.push(y);
if(dis[t]) return true;
}
}
return false;
}
int dfs(int x,int flow)
{
if(x==t||!flow) return flow;
int cur = flow;
for(int i=in[x];i;i=e[i].lt)
{
int y=e[i].to;
if(dis[y]==dis[x]+1&&e[i].f)
{
int tmp=dfs(y,min(cur,e[i].f));
e[i].f-=tmp; e[i^1].f+=tmp;
cur-=tmp; if(!cur) return flow;
}
}
dis[x] = -1;
return flow-cur;
}
int dinic()
{
int ans=0;
while(bfs()) ans+=dfs(s,inf);
return ans;
}
int build(int state)
{
init(); int one=0;
for(int i=0;i<p;i++)
if(state>>i&1)
{
add(s,bel[i+1],inf);
one++;
}
for(int i=1;i<=Ecnt;i++)
{
int x=E[i].x,y=E[i].y,w=E[i].w;
if(out[x]) x=t;
if(out[y]) y=t;
add(x,y,w);
}
return one;
}
}flow;
int main()
{
int x,y,w;
scanf("%d%d%d",&p,&n,&m);
for(int i=1;i<=p;i++) scanf("%lf%lf",&spc[i].x,&spc[i].y);
for(int i=1;i<=n;i++) scanf("%lf%lf",&stk[i].x,&stk[i].y);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&w);
li[++ed] = line(stk[x],stk[y]-stk[x]);
li[ed].x=x;li[ed].y=y;li[ed].w=w;
li[ed].another = ed+1;
e[x].push_back(ed);
li[++ed] = line(stk[y],stk[x]-stk[y]);
li[ed].x=y;li[ed].y=x;li[ed].w=w;
li[ed].another = ed-1;
e[y].push_back(ed);
}
for(int i=1;i<=n;i++) sort(e[i].begin(),e[i].end(),cmp);
for(int i=1;i<=ed;i++) if(!li[i].flag) find(i,++blk);
for(int i=1;i<=ed;i++) E[++Ecnt] = Edge(li[i].flag,li[li[i].another].flag,li[i].w);
//for(int i=1;i<=ed;i++) printf("%d %d\n",i,li[i].flag);
memset(ans,48,sizeof(ans));
int top=(1<<p);
//for(int i=1;i<=p;i++) printf("%d\n",bel[i]);
for(int i=1;i<top;i++)
{
int one=flow.build(i);
int tmp=flow.dinic();
//printf("===%d %d %d\n",i,one,tmp);
ans[one]=min(ans[one],tmp);
}
for(int i=p;i;i--) ans[i]=min(ans[i],ans[i+1]);
for(int i=1;i<=p;i++) printf("%d\n",ans[i]);
return 0;
}