| 记录编号 |
236192 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
| 题目名称 |
[JLOI 2014]镜面通道 |
最终得分 |
100 |
| 用户昵称 |
 zys |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
3.836 s |
| 提交时间 |
2016-03-13 09:46:23 |
内存使用 |
5.20 MiB |
显示代码纯文本
#define maxn 400
#define ll long long
#define dot2(x) (x<<1)
#define dot1(x) ((x<<1)-1)
#define rec(x) p[x].r
#define typ(x) p[x].type
#define circle(x) p[x].c
#define recl(x) p[x].r.left_low
#define recr(x) p[x].r.right_up
#define Min(a,b)((a)<(b)?(a):(b))
#define circle_center(x) p[x].c.center
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const int inf=0x2fffffff;
int n,right_boundary,up_boundary,cnt;ll dis;
int s,t,tot,first[maxn<<2],d[maxn<<2],q[maxn<<2],head,tail,cx,cy,cr,flow,ans;
struct Edge{
int u,v,next,w;
}edge[maxn*maxn<<1];
struct point{
int x,y;
};
struct circle{
point center;int r;
};
struct rectangle{
point left_low,right_up;
};
struct component{
bool type;
circle c;rectangle r;
}p[maxn];
void add(int u,int v,int w)
{
edge[tot].u=u;
edge[tot].v=v;
edge[tot].w=w;
edge[tot].next=first[u];
first[u]=tot++;
}
void Add(int u,int v,int w)
{
add(u,v,w);add(v,u,0);
}
bool bfs()
{
memset(d,0,sizeof(d));
head=tail=0;q[tail]=s;d[s]=1;
while(head<=tail){
int p=q[head++];
for(int i=first[p];i!=-1;i=edge[i].next)
if(edge[i].w>0&&(!d[edge[i].v])){
d[edge[i].v]=d[p]+1;
if(edge[i].v==t)return true;
q[++tail]=edge[i].v;
}
}
return false;
}
int dinic(int now,int f)
{
if(now==t||(!f))return f;
int tmp=f;
for(int i=first[now];i!=-1;i=edge[i].next)
if(edge[i].w>0&&d[edge[i].v]==d[now]+1){
int k=dinic(edge[i].v,Min(f,edge[i].w));
if(!k)d[edge[i].v]=0;
edge[i].w-=k;edge[i^1].w+=k;f-=k;
if(!f)break;
}
return tmp-f;
}
bool point_in_cir(point x,circle c)
{
return (ll)(x.x-c.center.x)*(ll)(x.x-c.center.x)+(ll)(x.y-c.center.y)*(ll)(x.y-c.center.y)<=(ll)c.r*(ll)c.r;
}
bool point_in_rec(point x,rectangle r)
{
return x.x<=r.right_up.x&&x.x>=r.left_low.x&&x.y<=r.right_up.y&&x.y>=r.left_low.y;
}
bool cross_circle(circle c1,circle c2)
{
dis=(ll)(c1.center.x-c2.center.x)*(ll)(c1.center.x-c2.center.x)+(ll)(c1.center.y-c2.center.y)*(ll)(c1.center.y-c2.center.y);
return (dis<=(ll)(c1.r+c2.r)*(ll)(c1.r+c2.r))&&(dis>(ll)(c1.r-c2.r)*(ll)(c1.r-c2.r));
}
bool cross_rec_circle(circle c,rectangle r)
{
cx=c.center.x;cy=c.center.y;cr=c.r;cnt=0;
if(cx+cr<=r.right_up.x&&cx-cr>=r.left_low.x&&cy+cr<=r.right_up.y&&cy-cr>=r.left_low.y)return false;
if(point_in_cir(r.left_low,c))cnt++;
if(point_in_cir(r.right_up,c))cnt++;
if(point_in_cir((point){r.left_low.x,r.right_up.y},c))cnt++;
if(point_in_cir((point){r.right_up.x,r.left_low.y},c))cnt++;
if(cnt>0&&cnt<4)return true;
if((ll)(cx-r.right_up.x)*(ll)(cx-r.right_up.x)<=(ll)cr*(ll)cr&&r.right_up.y>=cy&&r.left_low.y<=cy)return true;
if((ll)(cy-r.right_up.y)*(ll)(cy-r.right_up.y)<=(ll)cr*(ll)cr&&r.right_up.x>=cx&&r.left_low.x<=cx)return true;
if((ll)(cx-r.left_low.x)*(ll)(cx-r.left_low.x)<=(ll)cr*(ll)cr&&r.right_up.y>=cy&&r.left_low.y<=cy)return true;
if((ll)(cy-r.left_low.y)*(ll)(cy-r.left_low.y)<=(ll)cr*(ll)cr&&r.right_up.x>=cx&&r.left_low.x<=cx)return true;
return false;
}
bool cross_rec(rectangle r1,rectangle r2)
{
cnt=0;
if(point_in_rec(r2.left_low,r1))cnt++;
if(point_in_rec(r2.right_up,r1))cnt++;
if(point_in_rec((point){r2.left_low.x,r2.right_up.y},r1))cnt++;
if(point_in_rec((point){r2.right_up.x,r2.left_low.y},r1))cnt++;
if((!cnt)||cnt==4)return false;return true;
}
void renew(){for(int i=0;i<tot;i+=2) edge[i].w+=edge[i^1].w,edge[i^1].w=0;}
int min_cut()
{
int maxflow=0;
while(bfs())while(flow=dinic(s,inf)) maxflow+=flow;
return maxflow;
}
int main()
{
freopen("JLOI_mirror.in","r",stdin);
freopen("JLOI_mirror.out","w",stdout);
memset(first,-1,sizeof(first));
scanf("%d%d%d",&right_boundary,&up_boundary,&n);t=(n<<1)+1;
for(int i=1,k;i<=n;i++){
scanf("%d",&k);
if(k==1)scanf("%d%d%d",&circle_center(i).x,&circle_center(i).y,&circle(i).r),typ(i)=1;
else scanf("%d%d%d%d",&recl(i).x,&recl(i).y,&recr(i).x,&recr(i).y),typ(i)=0;
}
for(int i=1;i<=n;i++)Add(dot1(i),dot2(i),1);
for(int i=1;i<=n;i++)
if(typ(i)&&circle_center(i).y+circle(i).r>=up_boundary)Add(s,dot1(i),inf);
else if((!typ(i))&&recr(i).y>=up_boundary)Add(s,dot1(i),inf);
for(int i=1;i<=n;i++)
if(typ(i)&&circle_center(i).y-circle(i).r<=0)Add(dot2(i),t,inf);
else if(!typ(i)&&recl(i).y<=0)Add(dot2(i),t,inf);
for(int i=n;i>=1;i--)for(int j=n;j>i;j--){
if(typ(i)&&typ(j)){if(cross_circle(circle(i),circle(j)))Add(dot2(i),dot1(j),inf),Add(dot2(j),dot1(i),inf);}
else if((typ(i)&&(!typ(j)))||(typ(j)&&(!typ(i)))){
if(typ(i)){if(cross_rec_circle(circle(i),rec(j)))Add(dot2(i),dot1(j),inf),Add(dot2(j),dot1(i),inf);}
else if(cross_rec_circle(circle(j),rec(i)))Add(dot2(i),dot1(j),inf),Add(dot2(j),dot1(i),inf);
}
else{if(cross_rec(rec(i),rec(j)))Add(dot2(i),dot1(j),inf),Add(dot2(j),dot1(i),inf);}
}
while(bfs())while(flow=dinic(s,inf))ans+=flow;printf("%d\n",ans);
for(int i=1;i<=n;i++){
renew(),edge[(i<<1)-2].w=0;
if(min_cut()==ans-1) ans--,printf("%d ",i);
else edge[(i<<1)-2].w=1;
}
}