[JSOI2010 Frozen Nova 冷冻波]二分答案、最大流、还有一些琐碎的几何判定

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1822
【算法分析】
非常裸的模型。
求圆到线段的距离可以利用海伦公式+勾股定理。
然后剩下的就是二分时间+一个二分图匹配了。因为巫妖可能发多次，所以用网络流实现。
【其它】之前WA了∞遍，今天重敲。。。我靠，1Y。
【CODE】
#include #include #include #include #include #define sqr(x) ((x)*(x))
#define eps 1e-6
using namespace std;
const int maxn=205*2;
int Li,Wi,Tr;
bool v[maxn][maxn];
struct Lich_t{int x,y,r,t;}Lich[maxn];
struct Wise_t{int x,y;}Wise[maxn];
struct Tree_t{int x,y,r;}Tree[maxn];
struct Graph_t{
struct edge{int x,y,c;edge *next,*op;}g[maxn*maxn*4],*ls[maxn],*cur[maxn],*fa[maxn];
int d[maxn],gap[maxn],Flow,e,S,T;

void clr(){e=0; memset(ls,0,sizeof(ls));}

void add(int x,int y,int c){
g[++e].x=x; g[e].y=y; g[e].c=c; g[e].next=ls[x]; ls[x]=&g[e]; g[e].op=&g[e+1];
g[++e].x=y; g[e].y=x; g[e].c=0; g[e].next=ls[y]; ls[y]=&g[e]; g[e].op=&g[e-1];
}

void relabel(int p){
cur[p]=ls[p];
int mm=T;
for (edge *t=ls[p];t;t=t->next)
if (t->c && d[t->y] mm=d[t->y];
d[p]=mm+1;
}

void change(){
Flow++;
for (int i=T;i!=S;i=fa[i]->x){
fa[i]->c–;
fa[i]->op->c++;
}
}

void sap(){
int i;
Flow=0;
for (i=1;i<=T;i++){
cur[i]=ls[i];
d[i]=0;
gap[i]=0;
}
gap[0]=T;
i=S;
while (d[S] for (edge *&t=cur[i];t;t=t->next)
if (t->c && d[t->y]+1==d[t->x]) break;
if (cur[i]){
fa[cur[i]->y]=cur[i];
i=cur[i]->y;
if (i==T){
change();
i=S;
}
}else{
if (!–gap[d[i]]) break;
relabel(i);
++gap[d[i]];
if (i!=S) i=fa[i]->x;
}
}
}
}G;

inline int dis(int &X1,int &Y1,int &X2,int &Y2){return sqr(X1-X2)+sqr(Y1-Y2);}
inline double S(double &a,double &b,double &c){
double p=(a+b+c)/2;
return sqrt(p*(p-a)*(p-b)*(p-c));
}

bool Can(Lich_t L,Wise_t W){
if (dis(L.x,L.y,W.x,W.y)>sqr(L.r)) return false;
for (int i=1;i<=Tr;i++){
Tree_t &T=Tree[i];
double a,b,c,d;
a=sqrt(dis(W.x,W.y,T.x,T.y));
b=sqrt(dis(W.x,W.y,L.x,L.y)); if (b==0) b=eps;
c=sqrt(dis(L.x,L.y,T.x,T.y));
if (b*b+c*c>a*a && a*a+b*b>c*c) d=S(a,b,c)*2/b;
else d=min(a,c);
if (d+eps<=T.r) return false;
}
return true;
}

void init(){
ios::sync_with_stdio(false);
memset(v,false,sizeof(v));
cin >> Li >> Wi >> Tr;
for (int i=1;i<=Li;i++)
cin >> Lich[i].x >> Lich[i].y >> Lich[i].r >> Lich[i].t;
for (int i=1;i<=Wi;i++)
cin >> Wise[i].x >> Wise[i].y;
for (int i=1;i<=Tr;i++)
cin >> Tree[i].x >> Tree[i].y >> Tree[i].r;
for (int i=1;i<=Li;i++)
for (int j=1;j<=Wi;j++)
if (Can(Lich[i],Wise[j]))
v[i][j]=true;
}

bool Try(int Limit){
G.clr(); G.S=Li+Wi+1; G.T=Li+Wi+2;
for (int i=1;i<=Li;i++)
G.add(G.S,i,Limit/Lich[i].t+1);
for (int i=1;i<=Wi;i++)
G.add(Li+i,G.T,1);
for (int i=1;i<=Li;i++)
for (int j=1;j<=Wi;j++)
if (v[i][j]) G.add(i,Li+j,1);
G.sap();
if (G.Flow==Wi) return true;
return false;
}

void solve(){
int l=0,r=1000000000,mid;
while (l mid=(l+r)/2;
if (Try(mid)) r=mid;
else l=mid+1;
}
if (!Try(l)) cout << "-1n";
else cout << l << "n";
}

int main(){
init();
solve();
return 0;
}