Nova
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1349 Accepted Submission(s): 253
Problem Description
The Lich is a powerful hero that he can kill a wisp with his skill Frost Nova. The Burning Legion wants to conquer the forest so they sent some liches to kill all the wisps. A lich can kill a wisp once he could see the wisp and the wisp in his attack range. So the lich can attack a wisp when the distance between them is less than or equal to specific R and no trees are on the segment between the lich and wisp. Each lich has a cool down time that once he used Frost Nova he has to wait a few seconds for the next attack. Different liches may have different attack range and cool down time. The Lich King is the leader of the Burning Legion and he wants to arrange the attack order so the liches can wipe out all the wisps as soon as possible.
Input
The first line consists of an integer T, indicating the number of test cases.
The first line of each case consists of three integers N, M, K, indicating the number of lich, the number of wisps and the number of trees. The next N lines, each line consists of four integers x, y, r, t indicating the coordinate of that a lich, the radius of the attack range that lich’s Frost Nova can reach and the value of cool down time. The next M lines, each line consists of two integers x, y indicating the coordinate of each wisp. The last K lines, each line consists of three integers x, y, r, indicating the coordinate and radius of a tree. A lich cannot attack a wisp if the segment between them has a common point with the tree. The lich, wisp and trees will not overlap with each other.
Output
Output the minimum time lich need to kill all the wisps on a single line, or -1 if lich cannot kill all the wisps.
Constrains
0 < T <= 20
0 <= N, M, K <= 200
-10000 <= x, y <= 10000
0 <= r, t <= 10002
Sample Input
1
2 3 1
-100 0 100 3
100 0 100 5
-100 -10
100 10
110 11
5 5 10
Sample Output
5
Source
2009 Asia Wuhan Regional Contest Online
Recommend
lcy | We have carefully selected several similar problems for you: 3124 3127 3125 3123 3118
題目大意：
一共有N個巫師，一共有M個敵人，K棵樹。
給你N個巫師的坐标，攻擊範圍半徑，以及攻擊周期，再給你M個敵人的坐标，以及K棵樹的坐标以及其半徑。
如果敵人在巫師的攻擊範圍之内，那麼如果其兩點之間連線間不會有樹阻擋，那麼這個巫師就可以消滅這個敵人。問消滅掉所有敵人需要的最少的時間。如果不能消滅所有的敵人，輸出-1。
思路（碼農題）：
1、首先我們O（N*M*K）的預處理出這M個敵人都能被哪些巫師殺死。并且記錄起來，（代碼中抄襲了别人的計算幾何部分的闆子，計算幾何蒟蒻T T）。
2、然後我們考慮這樣一個單調性：随着時間的增多，那麼其最優配置設定情況能夠殺死的敵人也就越多，其滿足單調性，顯然我們能夠二分這個時間，來處理這個問題。考慮目前二分到的值mid：
①設定源點，連入每一個敵人，流設定為1.
②設定彙點，将每個巫師連入彙點，流設定為其時間/攻擊周期+1.
③将每個敵人連入能夠殺死其自己的巫師節點，流設定為1.
然後跑最大流，如果最大流==m，那麼說明目前最優情況是可以在mid這個時間内殺死所有敵人的。
然後繼續二分，記錄最優解即可。
Ac代碼：
#include<stdio.h>
#include<queue>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
struct node
{
int from;
int to;
int w;
int next;
}e[20000000];
struct Point
{
double x,y;
}p[10];
struct node1
{
int x,y,r,z;
}a[6000];
int divv[6000];
int cur[6000];
int head[6000];
int dian[600][2];
int tree[600][3];
int map[300][300];
const double eps=1e-7;
int n,m,k,cont,ss,tt;
int add(int from,int to,int w)
{
e[cont].to=to;
e[cont].w=w;
e[cont].next=head[from];
head[from]=cont++;
}
void Getmap(int mid)
{
memset(head,-1,sizeof(head));
cont=0;
ss=n+m+1;
tt=ss+1;
for(int i=0;i<m;i++)
{
add(ss,i,1);
add(i,ss,0);
}
for(int i=0;i<n;i++)
{
add(i+m,tt,mid/a[i].z+1);
add(tt,i+m,0);
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(map[i][j]==1)
{
add(i,j+m,1);
add(j+m,i,0);
}
}
}
}
int makedivv()
{
queue<int >s;
s.push(ss);
memset(divv,0,sizeof(divv));
divv[ss]=1;
while(!s.empty())
{
int u=s.front();
if(u==tt)return 1;
s.pop();
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].to;
int w=e[i].w;
if(w&&divv[v]==0)
{
divv[v]=divv[u]+1;
s.push(v);
}
}
}
return 0;
}
int Dfs(int u,int maxflow,int tt)
{
if(u==tt)return maxflow;
int ret=0;
for(int &i=cur[u];i!=-1;i=e[i].next)
{
int v=e[i].to;
int w=e[i].w;
if(w&&divv[v]==divv[u]+1)
{
int f=Dfs(v,min(maxflow-ret,w),tt);
e[i].w-=f;
e[i^1].w+=f;
ret+=f;
if(ret==maxflow)return ret;
}
}
return ret;
}
int Slove(int mid)
{
Getmap(mid);
int ans=0;
while(makedivv()==1)
{
memcpy(cur,head,sizeof(head));
ans+=Dfs(ss,0x3f3f3f3f,tt);
}
if(ans==m)return 1;
else return 0;
}
double Distance(Point a, Point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)*1.0 + 1.0*(a.y-b.y)*(a.y-b.y));
}
double xmult(Point p1, Point p2, Point p)
{
return (p1.x-p.x)*(p2.y-p.y) - (p2.x-p.x)*(p1.y-p.y);
}
double disptoseg(Point p, Point a ,Point b)
{
Point t = p;
t.x += a.y-b.y, t.y += b.x-a.x;
if(xmult(a,t,p)*xmult(b,t,p)>eps)
return Distance(p,a) < Distance(p,b)? Distance(p,a) : Distance(p,b);
return fabs(xmult(p, a, b))/Distance(a, b);
}
void init()
{
memset(map,0,sizeof(map));
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
p[0].x=(double)(dian[i][0]);
p[0].y=(double)(dian[i][1]);
p[1].x=(double)(a[j].x);
p[1].y=(double)(a[j].y);
double rr=(double)(a[j].r);
if(Distance(p[0],p[1])<=rr)
{
int flag=0;
for(int kk=0;kk<k;kk++)
{
p[2].x=(double )(tree[kk][0]);
p[2].y=(double )(tree[kk][1]);
double tmpp=(double )(tree[kk][2]);
if(disptoseg(p[2],p[0],p[1])<=tmpp)
{
flag=1;
}
}
if(flag==0)
{
map[i][j]=1;
}
}
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&m,&k);
int maxn=0;
for(int i=0;i<n;i++)
{
scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].r,&a[i].z);
maxn=max(a[i].z,maxn);
}
for(int i=0;i<m;i++)
{
scanf("%d%d",&dian[i][0],&dian[i][1]);
}
for(int i=0;i<k;i++)
{
scanf("%d%d%d",&tree[i][0],&tree[i][1],&tree[i][2]);
}
init();
int mid;
int ans=-1;
int l=0;
int r=m*maxn+100;
while(r>=l)
{
mid=(l+r)/2;
if(Slove(mid)==1)
{
r=mid-1;
ans=mid;
}
else l=mid+1;
}
printf("%d\n",ans);
}
}
![面試題精選:求根号2簡單？進階算法你肯定不會[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)