Missile


Time Limit: 2 Seconds      Memory Limit: 65536 KB

You control N missile launching towers. Every tower has enough missiles, but for each tower only one missile can be launch at the same time. Before the launching, every missile need T1 seconds to leave the tower. Assume that all the missiles have the same speed V, and it would fly along the shortest path to the target. You can just consider the horizontal distance and ignore the height. You can consider the time equal to distance / V (minutes). The missile can immediately destroy the target when it reached. Besides, for the same tower, after launching a missile, it need T2 minutes to prepare for the next one.

Now, give you the coordinate position of N missile launching towers and M targets, T1, T2 and V, you should find the minimum minutes to destroy all the targets.

Input

The input will consist of about 10 cases. The first line of each case contains five positive integer numbers N, M, T1, T2 and V, decribed as above. The next M lines contains two integer numbers indicating the coordinate of M targets. The continueing N lines contains two integer numbers indicating the coordinate of N towers.
To all the
cases, 1 ≤ N ≤ 50, 1 ≤ M ≤ 50
The absolute value of all the
coordinates will not exceed 10000, T1,
T2, V will not exceed 2000.

Output

For each case, the output is only one line containing only one real number
with six digits precision (after a decimal point) indicating the minimum minutes
to destroy all the targets.

Sample Input

3 3 30 20 1
0 0
0 50
50 0
50 50
0 1000
1000 0

Sample Output

91.500000

The question : use N A missile tower attack M Goals . Each missile launching tower can only serve one missile at the same time , Launching a missile requires T1( This is in seconds ) Time to leave the current missile tower , The time of a missile from launching to hitting the target is related to the distance from the target to the launching tower ( Linear distance ), After each missile is launched, the launch tower needs T2 Time to prepare for the next . Now give N Two missile towers and M The location coordinates of the target and T1,T2,V, Ask with this N How long does it take at least for a missile launch tower to destroy all M Goals .

Concrete realization

One : For every missile launcher , It's hitting a target with a total of M In this case : For the first time at the launch tower 、 The second launch 、 Third launch ... All the way to M Secondary emission . So we can split each missile tower into M A launch tower , They are the same distance from the same target , The only difference is T1、T2 It's not the same time .

Two : In this way, we get N*M A point transmitter to M A mapping of goals , The relationship is the time taken by the current tower to hit the target .

3、 ... and : Set up a super source 0, Super sink N * M + M + 1.

Four : Super source point to each tower ( After the split ) Lead a line with a capacity of 1 The edge of , Each target leads to a super sink with a capacity of 1 The edge of , If it is less than the current query time ( The same as the matching edge ) The capacity of edge construction is 1.

Then run the maximum flow , Determine whether the maximum flow is M. And then we look in two .

The above analysis comes from President da da :http://blog.csdn.net/hpuhjh/article/details/47334625

Too weak.   This problem can't be mapped out by itself ,

//#include<stdio.h>
//#include<string.h>
//#include<math.h>
//#include<queue>
//#include<stack>
//#include<algorithm>
//#define MAX 110
//#define DD double
//#define INF 0x7fffff
//#define MAXM 500100
//using namespace std;
//struct node
//{
// int from,to,cap,flow,next;
//}edge[MAXM];
//int dis[MAX],vis[MAX];
//int cur[MAX];
//int ans,head[MAX];
//int n,m;
//DD t1,t2,v;
////DD toalx[MAX],toaly[MAX],towrx[MAX],towry[MAX];
//struct record
//{
// DD x,y;
//};
//DD time[3000][MAX];
//DD map[MAX][MAX];
//void init()
//{
// ans=0;
// memset(head,-1,sizeof(head));
//}
//void add(int u,int v,int w)
//{
// edge[ans]={u,v,w,0,head[u]};
// head[u]=ans++;
// edge[ans]={v,u,0,0,head[v]};
// head[v]=ans++;
//}
//DD dist(record a,record b)
//{
// return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
//}
//record towr[MAX];
//record toal[MAX];
//void input()
//{
// int i,j,k;
//
// for(i=1;i<=m;i++)
// scanf("%lf%lf",&toal[i].x,&toal[i].y);
// for(i=1;i<=n;i++)
// scanf("%lf%lf",&towr[i].x,&towr[i].y);
// for(i=1;i<=n;i++)
// for(j=1;j<=m;j++)
// map[i][j]=dist(towr[i],toal[j]);
// for(i=1;i<=n;i++)
// for(k=1;k<=m;k++)
// for(j=1;j<=m;j++)
// time[(i - 1) * m + k][j] = t1 * k + t2 * (k - 1) + map[i][j] / v;
//}
//void getmap(double Max)
//{
// int i,j;
// for(i=1;i<=n*m;i++)
// add(0,i,1);
// for(i=n*m+1;i<=n*m+m;i++)
// add(i,n*m+m+1,1);
// for(i=1;i<=n*m;i++)
// {
// for(j=1;j<=m;j++)
// {
// if(time[i][j]<=Max)
// add(i,j+n*m,1);
// }
// }
//}
//
//
//int bfs(int beg,int end)
//{
// queue<int>q;
// memset(vis,0,sizeof(vis));
// memset(dis,-1,sizeof(dis));
// while(!q.empty()) q.pop();
// vis[beg]=1;
// dis[beg]=0;
// q.push(beg);
// while(!q.empty())
// {
// int u=q.front();
// q.pop();
// for(int i=head[u];i!=-1;i=edge[i].next)
// {
// node E=edge[i];
// if(!vis[E.to]&&E.cap>E.flow)
// {
// dis[E.to]=dis[u]+1;
// vis[E.to]=1;
// if(E.to==end) return 1;
// q.push(E.to);
// }
// }
// }
// return 0;
//}
//int dfs(int x,int a,int end)
//{
// if(x==end||a==0)
// return a;
// int flow=0,f;
// for(int& i=cur[x];i!=-1;i=edge[i].next)
// {
// node& E=edge[i];
// if(dis[E.to]==dis[x]+1&&(f=dfs(E.to,min(a,E.cap-E.flow),end))>0)
// {
// E.flow+=f;
// edge[i^1].flow-=f;
// flow+=f;
// a-=f;
// if(a==0) break;
// }
// }
// return flow;
//}
//int maxflow(int beg,int end)
//{
// int flow=0;
// while(bfs(beg,end))
// {
// memcpy(cur,head,sizeof(head));
// flow+=dfs(beg,INF,end);
// }
// return flow;
//}
//int main()
//{
// int t;
// while(scanf("%d%d%lf%lf%lf",&n,&m,&t1,&t2,&v)!=EOF)
// {
// t1=t1/60;
// input();
// double l=0.0, r =200000000000.0,mid;
// while(r-l>=1e-8)
// {
// mid=(l+r)/2;
// init();
// getmap(mid);
// if(maxflow(0,n*m+m+1)>=m)
// r=mid;
// else
// l=mid;
// }
// printf("%.6lf\n",r);
// }
// return 0;
//} #include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
#define INF 0x3f3f3f3f
#define maxn 5000
#define maxm 500000
using namespace std; int head[maxn], cur[maxn], cnt;
int dist[maxn], vis[maxn];
struct node
{
int u,v,cap,flow,next;
};
struct NODE
{
double x, y;
};
node edge[maxm];
NODE tower[60];
NODE target[60];
int N, M;
double T1, T2, V;
double map[60][60];
double Time[3000][60];
double change(NODE a, NODE b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
void init()
{
cnt = 0;
memset(head, -1, sizeof(head));
}
void add(int u, int v, int w){
node E1 = {u, v, w, 0, head[u]};
edge[cnt] = E1;
head[u] = cnt++;
node E2 = {v, u, 0, 0, head[v]};
edge[cnt] = E2;
head[v] = cnt++;
}
void getmap(double max_min)
{
int i, j;
for(i = 1; i <= N * M; ++i)
add(0, i, 1);
for(i = N * M + 1; i <= N * M + M; ++i)
add(i, N * M + M + 1, 1);
for(i = 1; i <= N * M; ++i)
for(j = 1; j <= M; ++j)
if(Time[i][j] <= max_min)// Find the minimum time to build a map
add(i, j + N * M, 1);
}
bool BFS(int st, int ed)
{
queue<int>q;
memset(vis, 0, sizeof(vis));
memset(dist, -1, sizeof(dist));
q.push(st);
vis[st] = 1;
dist[st] = 0;
while(!q.empty()){
int u = q.front();
q.pop();
for(int i = head[u]; i != -1; i = edge[i].next){
node E = edge[i];
if(!vis[E.v] && E.cap > E.flow){
vis[E.v] = 1;
dist[E.v] = dist[u] + 1;
if(E.v == ed) return true;
q.push(E.v);
}
}
}
return false;
}
int DFS(int x, int ed, int a)
{
if(a == 0 || x == ed)
return a;
int flow = 0, f;
for(int &i = cur[x]; i != -1; i =edge[i].next)
{
node &E = edge[i];
if(dist[E.v] == dist[x] + 1 && (f = DFS(E.v, ed, min(a, E.cap - E.flow))) > 0){
E.flow += f;
edge[i ^ 1].flow -= f;
flow += f;
a -= f;
if(a == 0) break;
}
}
return flow;
} int maxflow (int st, int ed)
{
int flowsum = 0;
while(BFS(st, ed))
{
memcpy(cur, head, sizeof(head));
flowsum += DFS(st, ed, INF);
}
return flowsum;
}
int main ()
{
while(scanf("%d%d%lf%lf%lf", &N, &M, &T1, &T2, &V) != EOF){
T1 = T1 / 60;//t1 The unit given is seconds To convert to sub
int i, j, k;
for(j = 1; j <= M; ++j)
scanf("%lf%lf", &target[j].x, &target[j].y);
for(i = 1; i <= N; ++i)
scanf("%lf%lf", &tower[i].x, &tower[i].y);
for(i = 1; i <= N; ++i)
for(j = 1; j <= M; ++j)
map[i][j] = change(tower[i], target[j]);
//map[][] It means the first one i A tower to j The distance between two targets
for(i = 1; i <= N; ++i)
for(k = 1; k <= M; ++k)//k It means to launch the second k A missile
{
for(j = 1; j <= M; ++j)
Time[(i - 1) * M + k][j] = T1 * k + T2 * (k - 1) + map[i][j] / V;
//Time[][] Array representation from the second i The time required for each tower to fire shells to each target in turn
}
double l = 0.0, r = 200000000000.0, mid;
while(r - l >= 1e-8)
{
mid = (l + r) / 2;
init();
getmap(mid);// Every time you add a map
if(maxflow(0, N * M + M + 1) >= M)
r = mid;
else
l = mid;
}
printf("%.6lf\n", r);
}
return 0;
}

zoj 3460 Missile【 Classic mapping && Two points 】 More articles about

  1. hdoj--5093--Battle ships( Classical construction of bipartite graphs )

    Battle ships Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Tot ...

  2. poj--1149--PIGS( Maximum flow classical mapping )

    PIGS Time Limit: 1000MS   Memory Limit: 10000KB   64bit IO Format: %I64d & %I64u Submit Status D ...

  3. BZOJ-1822 Frozen Nova Cold wave meter (jie) count (xi) The geometric + Two points + Maximum flow determination + Classic mapping

    This is a compelling question ! Feel the deep malice of mathematics to me (#‵′).... 1822: [JSOI2010]Frozen Nova Cold wave Time Limit: 10 Sec Memory Limit: 64 MB S ...

  4. 【ARC069F】Flags 2-sat+ Line tree optimizes drawing + Two points

    Description ​ There is... On the axis n A flag , The first ii One can be inserted in coordinates xi perhaps yi, Maximize the minimum distance between two flags . Input ​ The first line is an integer N. ​ Next N Two integers per line xi, ...

  5. POJ 2226 Minimum point coverage ( Classic mapping )

    Muddy Fields Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 8881   Accepted: 3300 Desc ...

  6. hdu 4185 Oil Skimming( Bipartite map matching Classic mapping + The Hungarian template )

    Problem Description Thanks to a certain "green" resources company, there is a new profitab ...

  7. 2-sat——poj3678 Classic mapping

    More classic construction , See the advanced guide for details 2-sat In general, we need to use tarjan To find the strongly connected component /*2-sat What we want to add is the edge with mandatory relationship */ #include<iostream> #include<cs ...

  8. Network flow -- Maximum flow --POJ 2139( Super source and sink + Demolition site construction + Two points +Floyd)

    Description FJ's cows really hate getting wet so much that the mere thought of getting caught in the ...

  9. hdu4560 Good mapping , Dichotomous maximum flow

    The question : I am a singer Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Subm ...

Random recommendation

  1. VC Method call order

    VC1,push VC2  vc2 pop To vc1  Half right , Then cancel vc1 present To vc2  vc2 dismiss To vc1  push and present Is different . In two ways vc ...

  2. php standard

    PSR-0 Automatic loading PSR-1 Basic code specifications PSR-2 Code style PSR-3 Log interface

  3. OpenSuse Compile below MonoDevelop

    When accessing Monodevelop.com The installation package downloaded from the official website , After installation , It's not the latest version . stay OpenSuse The download is 3.0 edition . According to the instructions on the official website , You can download the source code to compile . According to the guidelines on the official website : 1. $ git clo ...

  4. analysis jQuery in extend Method -- usage 《 One 》

    extend Method in jQuery Is a very important method ,jQuey It's used internally to extend property methods . Common words jQuery Plug-in development . jQuery Two methods are provided ,$.extend and $.fn.extend, The two methods are implemented internally ...

  5. LNK4098: Default library “MSVCRT” Conflicts with the use of other libraries

    LNK4098: Default library "MSVCRT" Conflicts with the use of other libraries The method of modification : In project properties , At the connector - In the input options , Add the corresponding library to the ignore specific library , Please refer to the table below for details . The following ...

  6. Front end interview questions sorting —Vue piece

     1. Yes vue The understanding of the , What are the characteristics of ,vue Why not compatible IE8 And the following browsers vue Is a progressive framework for building user interfaces , The core is a responsive data binding system vue Is a MVVM frame , Based on bidirectional binding data , When data happens ...

  7. Educational Codeforces Round 5

    616A - Comparing Two Long Integers    20171121 Just direct violence ... There's nothing to say #include<stdlib.h> #include&l ...

  8. python Recursion and dichotomy

    1. recursive Call yourself The entry to recursion ( Parameters ) and exit (return) Traversal of tree structure import os def func(lujing, n): lst = os.listdir(lujing) ...

  9. Why rewrite equals I'll rewrite it later hashCode

    equals and hashCode The relationship between To understand the problems in the title, we must understand equals Methods and hashCode What are the methods , And the reason for its birth , When we understand this, in fact, the topic is not a problem , Next, let's discuss one ...

  10. LaTeX Mathematical formula input

    [ Roof placement Tips ] stay WinEdt Quickly add formula characters without manually typing one by one letters~: The following will appear GUI Page Control : ------------------------- ...