TYVJ1935 missile defense tower

Problem surface

Freda's castle was attacked by M invaders!

Freda controls N missile defense towers, each with a sufficient number of missiles, but can only launch one at a time.

When launching the missile, it takes T1 seconds for the missile to be launched from the defense tower, while after launching the missile, the defense tower that launches the missile takes T2 minutes to cool down.

All missiles have the same uniform speed V and will hit the target along the shortest path.

When calculating the Distance from the defense tower to the target, you only need to calculate the horizontal Distance, ignoring the altitude of the missile.

The flight time of the missile in the air is (Distance/V) minutes. The missile can destroy it immediately after it reaches the target.

Now, give the coordinates of N missile defense towers and the coordinates of M intruders, T1,T2 and V. Because Freda's little partner Rainbow is coming to visit the castle, you need to figure out at least how many minutes to repel all the invaders.

Input format

The first line contains five positive integers N,M,T1,T2,V.

The next M lines are two integers per line, representing the coordinates of the intruder.

The next N lines are two integers per line, representing the coordinates of the defense tower.

Output format

Output a real number indicating the minimum number of minutes it takes to hit all intruders, rounded to six decimal places.

Data range

1 ≤ N,M ≤ 50, the absolute value of coordinates shall not exceed 10000, T1, T2 and V shall not exceed 2000.

Input sample:

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

Output example:

91.500000

Problem solution

There are four solutions to multiple matching
1. Disassemble all points
2. The left point set can only be connected once. In the Hungarian algorithm, match the k-th connection of the right point in turn, and then re match the k-th connection of the right point in turn
3. The right point set can only be connected once, which can be exchanged into 2, or the left point can be matched k times in the Hungarian algorithm
4. Add source and sink points to the network flow and do it directly

In this problem, we use the slow down method of 3 to let the enemy match the bullets

The problem is monotonous, two minutes in time

Judge how many bullets each turret can fire during this time (up to 50, if more is useless, the enemy will have 50)

The enemy and the bullets that can hit him are connected, and Hungary is finished

#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;

const int N = 50 + 5;

int n, m, _, k;
int match[N * N], c;
db t1, t2, sp;
PII a[N], b[N];
bool v[N * N];

double dis(int x, int y) {
    return sqr(a[x].fi - b[y].fi) + sqr(a[x].se - b[y].se);
}

bool dfs(int x, double mid) {
    per (i, n * c, 1) {
        if (dis(x, (i - 1) / c + 1) > sqr(sp) * sqr(mid - (i - 1) % c * (t1 + t2) - t1)) continue;
        if (v[i]) continue;
        v[i] = 1;
        if (!match[i] || dfs(match[i], mid)) { match[i] = x; return 1; } 
    }
    return 0;
}

bool check(double mid) {
    c = (int)min((mid + t2) / (t1 + t2), 50.0);
    per (i, n * c, 1) match[i] = 0;
    rep (i, 1, m) {
        per (j, n * c, 1) v[j] = 0;
        if (!dfs(i, mid)) return 0; 
    }
    return 1;
}

int main() {
    IOS; cin >> n >> m >> t1 >> t2 >> sp; t1 /= 60;
    rep (i, 1, m) cin >> a[i].fi >> a[i].se;
    rep (i, 1, n) cin >> b[i].fi >> b[i].se;
    double l = 0, r = 2e18;
    while (r - l >= 1e-8) {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    cout << setiosflags(ios::fixed) << setprecision(6) << r;
    return 0;
}

Tags: Binary Search

Posted by JayBachatero on Sun, 15 May 2022 19:07:14 +0300