记录编号	494928	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[JLOI 2014]镜面通道	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	5.664 s
提交时间	2018-04-15 13:23:56	内存使用	0.57 MiB

#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define eps 1e-6
#define inf (int)1e9
using namespace std;
const int maxn=3100;
struct poi{double x,y;};
struct Dat{int x,y;}data[maxn];
struct circle{double x,y,r;}c[maxn];
struct matrix{double x1,y1,x2,y2;}m[maxn];
struct Edge{int from,to,cap,flow;};
int n,s,t,cnt1,cnt2,d[maxn],cur[maxn],belong[maxn];
vector<Edge>edges;
vector<int>G[maxn];
bool vis[maxn];
void addedge(int from,int to,int cap){
	edges.push_back((Edge){from,to,cap,0});
	edges.push_back((Edge){to,from,0,0});
	int m=edges.size();
	G[from].push_back(m-2),G[to].push_back(m-1);
}
bool bfs(){
	memset(vis,0,sizeof(vis));
	vis[s]=1;d[s]=0;
	queue<int>q;q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=0;i<(int)G[u].size();i++){
			Edge e=edges[G[u][i]];
			if(!vis[e.to]&&e.cap>e.flow)d[e.to]=d[u]+1,vis[e.to]=1,q.push(e.to);
		}
	}
	return vis[t];
}
int dfs(int x,int v){
	if(x==t||!v)return v;
	int f,flow=0;
	for(int&i=cur[x];i<(int)G[x].size();i++){
		Edge &e=edges[G[x][i]];
		if((d[e.to]==d[x]+1)&&(f=dfs(e.to,min(v,e.cap-e.flow)))>0){
			flow+=f,v-=f,e.flow+=f;
			edges[G[x][i]^1].flow-=f;
			if(!v)break;
		}
	}
	return flow;
}
int dinic(){
	int flow=0;
	while(bfs()){
		memset(cur,0,sizeof(cur));
		flow+=dfs(s,inf);
	}
	return flow;
}
double dist(poi x,poi y){return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));}
bool check(matrix x,matrix y){
	if(dist((poi){x.x1,x.y1},(poi){y.x1,y.y1})<=x.x2)return true;
	if(dist((poi){x.x1,x.y1},(poi){y.x1,y.y2})<=x.x2)return true;
	if(dist((poi){x.x1,x.y1},(poi){y.x2,y.y1})<=x.x2)return true;
	if(dist((poi){x.x1,x.y1},(poi){y.x2,y.y2})<=x.x2)return true;
	if(x.x1>=y.x1&&x.x1<=y.x2&&fabs(x.y1*2-y.y1-y.y2)<=y.y2-y.y1+x.x2*2)return true;
	if(x.y1>=y.y1&&x.y1<=y.y2&&fabs(x.x1*2-y.x1-y.x2)<=y.x2-y.x1+x.x2*2)return true;
	else return false;
}
bool judge(int u,int v){
	int id1=data[u].y,id2=data[v].y;
	if(data[u].x==1&&data[v].x==1){
		poi x=(poi){c[id1].x,c[id1].y};
		poi y=(poi){c[id2].x,c[id2].y};
		double dis=dist(x,y);
		if(dis-c[id1].r-c[id2].r<eps)return true;
		return false;
	}
	if(data[u].x==2&&data[v].x==2){
		if(m[id1].y2>=m[id2].y1&&m[id2].y2>=m[id1].y1&&
			m[id1].x2>=m[id2].x1&&m[id2].x2>=m[id2].x1)return true;
		else return false;
	}
	if(data[u].x==2&&data[v].x==1)swap(u,v),swap(id1,id2);
	return check((matrix){c[id1].x,c[id1].y,c[id1].r,0},m[id2]);
}
void renew(){
	for(int i=1;i<(int)edges.size();i+=2)
		edges[i].flow+=edges[i^1].flow,edges[i^1].flow=0;
}
int main(){
	freopen("JLOI_mirror.in","r",stdin);
	freopen("JLOI_mirror.out","w",stdout);
	double X,Y;
	scanf("%lf%lf%d",&X,&Y,&n);
	int op;s=0,t=1;
	for(int i=1;i<=n;i++){
		scanf("%d",&op);data[i].x=op;
		if(op==1){
			data[i].y=++cnt1;
			scanf("%lf%lf%lf",&c[cnt1].x,&c[cnt1].y,&c[cnt1].r);
			if(c[cnt1].y+c[cnt1].r>=Y)addedge(i<<1|1,t,inf);
			if(c[cnt1].y-c[cnt1].r<=eps)addedge(s,i<<1,inf);
		}
		else{
			data[i].y=++cnt2;
			scanf("%lf%lf%lf%lf",&m[cnt2].x1,&m[cnt2].y1,&m[cnt2].x2,&m[cnt2].y2);
			if(m[cnt2].y2>=Y)addedge(i<<1|1,t,inf);
			if(m[cnt2].y1<=eps)addedge(s,i<<1,inf);
		}
	}
	for(int i=1;i<=n;i++){
		addedge(i<<1,i<<1|1,1);
		belong[i]=G[i<<1|1][G[i<<1|1].size()-1]-1;
		for(int j=1;j<i;j++){
			if(judge(i,j))addedge(i<<1|1,j<<1,inf),addedge(j<<1|1,i<<1,inf);
		}
	}
	int ans=dinic();
	printf("%d\n",ans);
	for(int i=1;i<=n&&ans;i++){
		renew();
		edges[belong[i]].cap=0;
		if(dinic()==ans-1)ans--,printf("%d ",i);
		else edges[belong[i]].cap=1;
	}
	return 0;
}