记录编号	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;
	}
}