[JSOI2010]Frozen Nova 冷冻波.cpp

#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>
using namespace std;
const int MAXN=410;
const int inf=1e9;

struct Point {
	int x, y, r, t;
	Point(){}
	Point(int x, int y):x(x), y(y){}
	Point operator - (Point oth) {
		return Point(x-oth.x, y-oth.y);
	}
	double operator * (Point oth) {
		return x*oth.y-y*oth.x;
	}
	double operator ^ (Point oth) {
		return x*oth.x+y*oth.y;
	}
	double len() {
		return sqrt((double)x*x+(double)y*y);
	}
}Wi[MAXN], Tr[MAXN], Sp[MAXN];

struct Edge {
	int v, cap;
	Edge *next, *op;
	Edge(){}
	Edge(int v, int c, Edge *n):v(v), cap(c), next(n){}
}*E[MAXN];

vector<int> Ve[MAXN];
int level[MAXN], Q[MAXN];
int N, M, K, S, T;

inline double pointToSeg(Point A, Point B, Point O) {
	if (((O-A)^(B-A))>=0 && (((O-B)^(A-B))>=0) && (B-A).len()>0) return fabs(((O-A)*(B-A))/(B-A).len());
	else return min((O-A).len(), (O-B).len());
}

inline void addedge(int u, int v, int c) {
	E[u]=new Edge(v, c, E[u]); E[v]=new Edge(u, 0, E[v]);
	E[u]->op=E[v]; E[v]->op=E[u];
}

bool dinic_bfs() {
	memset(level, -1, sizeof(level));
	level[S]=0; Q[0]=S;
	for (int h=0, t=1; h<t; h++) {
		int u=Q[h], v;
		for (Edge *p=E[u]; p; p=p->next) 
			if (level[v=p->v]==-1 && p->cap>0) {
				level[v]=level[u]+1;
				Q[t++]=v;
			}
	}
	return (level[T]!=-1);
}

int dinic_dfs(int u, int low) {
	if (u==T) return low;
	int ret=0, tmp, v;
	for (Edge *p=E[u]; p && ret<low; p=p->next) 
		if (level[v=p->v]==level[u]+1 && p->cap>0) {
			if (tmp=dinic_dfs(v, min(low-ret, p->cap))) {
				ret+=tmp, p->cap-=tmp, p->op->cap+=tmp;
			}
		}
	if (!ret) level[u]=-1; return ret;
}

int dinic() {
	int maxflow=0, t;
	while (dinic_bfs()) {
		while (t=dinic_dfs(S, inf)) maxflow+=t;
	}
	return maxflow;
}

bool check(int Time) {
	S=0; T=N+M+1;
	memset(E, 0, sizeof(E));
	for (int i=1; i<=N; i++) addedge(S, i, Time/Wi[i].t+1);
	for (int i=1; i<=M; i++) addedge(i+N, T, 1);
	for (int i=1; i<=N; i++)
		for (int j=0; j<(int)Ve[i].size(); j++)
			addedge(i, Ve[i][j]+N, 1);
	return (dinic()==M);
}

int main() {
	scanf("%d%d%d", &N, &M, &K);
	for (int i=1; i<=N; i++) scanf("%d%d%d%d", &Wi[i].x, &Wi[i].y, &Wi[i].r, &Wi[i].t);
	for (int i=1; i<=M; i++) scanf("%d%d", &Sp[i].x, &Sp[i].y);
	for (int i=1; i<=K; i++) scanf("%d%d%d", &Tr[i].x, &Tr[i].y, &Tr[i].r);
	for (int i=1; i<=N; i++) {
		Ve[i].clear();
		for (int j=1; j<=M; j++) {
			if ((Wi[i]-Sp[j]).len()>Wi[i].r) continue;
			bool flag=true;
			for (int k=1; k<=K && flag; k++) 
				if (pointToSeg(Wi[i], Sp[j], Tr[k])<=Tr[k].r) flag=false;
			if (flag) Ve[i].push_back(j);
		}
	}
	int left=0, right=inf;
	while (left<right) {
		int mid=(left+right)>>1;
		if (check(mid)) right=mid;
		else left=mid+1;
	}
	if (right==inf) puts("-1");
	else printf("%d\n", right);
	return 0;
}