[JLOI 2014]镜面通道 - dashgua - 218112

记录编号	218112	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[JLOI 2014]镜面通道	最终得分	100
用户昵称	dashgua	是否通过	通过
代码语言	C++	运行时间	4.027 s
提交时间	2016-01-08 17:06:20	内存使用	46.61 MiB
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <ctime>
typedef std::pair<int,int> Vec;
typedef std::pair<long long,long long> VecL;
#define VEC(x, y) make_pair(x, y)
#define X first
#define Y second

const int maxn = 1005, maxe = maxn * maxn << 2, inf = 0x3f3f3f3f;

int N, cx, cy;
int cid[maxn], sid[maxn], cl, sl;
int in[maxn], out[maxn];

int head[maxn], el = 1, ind;

struct Edge
{
	int v, cap, next;
}edge[maxe];

int St, T, dep[maxn], cur[maxn];

void newedge(int u,int v,int w)
{
	edge[++el] = (Edge){v, w, head[u]}, head[u] = el;
	edge[++el] = (Edge){u, 0, head[v]}, head[v] = el;
}
Vec operator - (const Vec &a,const Vec &b)
{
	return std::VEC(a.X - b.X, a.Y - b.Y);
}
Vec operator + (const Vec &a,const Vec &b)
{
	return std::VEC(a.X + b.X, a.Y + b.Y);
}
long long cross(const Vec a,const Vec b)
{
	return (long long) a.X * b.Y - (long long) b.X * a.Y;
}
long long dotpro(const Vec a,const Vec b)
{
	return (long long) a.X * b.X + (long long) a.Y * b.Y;
}
bool onLine(Vec k,Vec a,Vec b)
{
	if(cross(a - k, b - k)) return false;
	return dotpro(a - k, b - k) <= 0;
}
long long sqr(long long x)
{
	return x * x;
}
struct Circle
{
	int x, y, r;
	
	bool incircle(Vec a)
	{
		return sqr(a.X - x) + sqr(a.Y - y) <= sqr(r);
	}
	bool check(Vec a,Vec b)
	{
		if(incircle(a) || incircle(b)) return true;
		
		Vec f = b - a, c = std::VEC(x, y);
		f.Y *= -1, std::swap(f.X, f.Y);
		
		long long P = (long long) f.X * (a.X - x) + (long long) f.Y * (a.Y - y);
		if((long double) P * P > (long double) r * r * (sqr(f.X) + sqr(f.Y))) return false;
		
		if(onLine(std::VEC(x, y), a, b)) c = c + f;
		
		return (long double) cross(f, a - c) * cross(f, b - c) < 0;
	}
}C[maxn];

struct Square
{
	int xl, yl, xr, yr;
	
	bool insquare(Vec a)
	{
		return a.X >= xl && a.X <= xr && a.Y >= yl && a.Y <= yr;
	}
	bool check(Vec a,Vec b)
	{
		return yl <= a.Y && yr >= a.Y && std::max(xl, a.X) <= std::min(xr, b.X);
	}
}S[maxn];

bool circle_check(Circle a,Circle b)
{
	return sqr(a.x - b.x) + sqr(a.y - b.y) <= sqr(a.r + b.r);
}
bool square_check(Square a,Square b)
{
	if(std::max(a.xl, b.xl) > std::min(a.xr, b.xr)) return false;
	if(std::max(a.yl, b.yl) > std::min(a.yr, b.yr)) return false;
	return true;
}
bool check(Circle a,Square b)
{
	if(b.insquare(std::VEC(a.x, a.y))) return true;
	if(a.incircle(std::VEC(b.xl, b.yl)) || a.incircle(std::VEC(b.xl, b.yr))) return true;
	if(a.incircle(std::VEC(b.xr, b.yl)) || a.incircle(std::VEC(b.xr, b.yr))) return true;
	if(a.check(std::VEC(b.xl, b.yl), std::VEC(b.xl, b.yr))) return true;
	if(a.check(std::VEC(b.xr, b.yl), std::VEC(b.xr, b.yr))) return true;
	if(a.check(std::VEC(b.xl, b.yl), std::VEC(b.xr, b.yl))) return true;
	if(a.check(std::VEC(b.xl, b.yr), std::VEC(b.xr, b.yr))) return true;
	return false;
}
void build()
{
	for(int i = 1; i <= N; i++)
	{
		in[i] = i, out[i] = N + i;
		newedge(in[i], out[i], 1);
	}
	
	St = (N << 1) + 1, T = ind = St + 1;
	Vec SL = std::VEC(0, 0), SR = std::VEC(cx, 0);
	Vec TL = std::VEC(0, cy), TR = std::VEC(cx, cy);
	
	for(int i = 1; i <= cl; i++)
	{
		if(C[i].check(SL, SR)) newedge(St, in[cid[i]], inf);
		if(C[i].check(TL, TR)) newedge(out[cid[i]], T, inf);
	}
	
	for(int i = 1; i <= sl; i++)
	{
		if(S[i].check(SL, SR)) newedge(St, in[sid[i]], inf);
		if(S[i].check(TL, TR)) newedge(out[sid[i]], T, inf);
	}
	
	for(int i = 1; i <= cl; i++)
		for(int j = 1; j <= cl; j++)
			if(i != j && circle_check(C[i], C[j]))
				newedge(out[cid[i]], in[cid[j]], inf);

	for(int i = 1; i <= sl; i++)
		for(int j = 1; j <= sl; j++)
			if(i != j && square_check(S[i], S[j]))
				newedge(out[sid[i]], in[sid[j]], inf);
	
	for(int i = 1; i <= cl; i++)
		for(int j = 1; j <= sl; j++)
			if(check(C[i], S[j]))
			{
				newedge(out[cid[i]], in[sid[j]], inf);
				newedge(out[sid[j]], in[cid[i]], inf);
			}
}
bool BFS()
{
	static int line[maxn];
	int f = 0, r = 0;
	
	for(int i = 1; i <= ind; i++) dep[i] = 0;
	
	line[r++] = T, dep[T] = 1;
	
	while(f != r)
	{
		int t = line[f++];
		
		for(int i = head[t]; i ; i = edge[i].next)
			if(edge[i ^ 1].cap)
			{
				int p = edge[i].v;
				
				if(!dep[p])
				{
					dep[p] = dep[t] + 1;
					line[r++] = p;
				}
			}
	}
	for(int i = 1; i <= ind; i++) cur[i] = head[i];
	
	return (bool) dep[St];
}
int DFS(int a,int flow)
{
	if(a == T || !flow) return flow;
	
	int ret = 0;
	
	for(int i = cur[a]; i ; i = edge[i].next)
	{
		int p = edge[i].v;
		
		if(dep[p] && dep[p] + 1 == dep[a])
		{
			int c = DFS(p, std::min(flow, edge[i].cap));
			
			edge[i].cap -= c;
			edge[i ^ 1].cap += c;
			flow -= c, ret += c;
			
			if(!flow)
			{
				cur[a] = i;
				return ret;
			}
		}
	}
	cur[a] = 0;
	
	return ret;
}
int Dinic()
{
	int maxflow = 0;
	
	while(BFS()) maxflow += DFS(St, inf);
	
	return maxflow;
}
void init()
{
	int x, y, r, xr, yr;
	
	scanf("%d%d%d", &cx, &cy, &N);
	
	for(int i = 1, tp; i <= N; i++)
	{
		scanf("%d", &tp);
		
		if(tp == 1)
		{
			scanf("%d%d%d", &x, &y, &r);
			C[++cl] = (Circle){x, y, r};
			cid[cl] = i;
		}
		else
		{
			scanf("%d%d%d%d", &x, &y, &xr, &yr);
			S[++sl] = (Square){x, y, xr, yr};
			sid[sl] = i;
		}
	}
}
void recovery()
{
	for(int i = 2; i <= el; i += 2)
	{
		edge[i].cap += edge[i ^ 1].cap;
		edge[i ^ 1].cap = 0;
	}
}
void solve()
{
	int maxf = Dinic();
	
	printf("%d\n", maxf);
	
	for(int i = 1; i <= N && maxf; i++)
	{
		int j = i << 1;
		
		recovery(), edge[j].cap = 0;
		
		if(Dinic() == maxf - 1)
			printf("%d ", i), maxf--;
		else
			edge[j].cap = 1;
	}
}
int main()
{
	freopen("JLOI_mirror.in","r",stdin);
	freopen("JLOI_mirror.out","w",stdout);
	
	init();
		
	build();
		
	solve();
	
	fclose(stdin);
	fclose(stdout);
	return 0;		
}