Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
- //#pragma GCC optimize("unroll-loops")
- //#pragma GCC optimize("Ofast")
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- #define pb push_back
- #define pii pair<int, int>
- #define mp make_pair
- #define loop(i, n) for(int i = 0; i < (int)n; ++i)
- #define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
- #define rloop(i, n) for (int i = (int)n; i >= 0; --i)
- #define F first
- #define S second
- #define sorted(a) sort(a.begin(), a.end())
- const long double EPS = 1e-9;
- struct Point {
- long double x; long double y;
- };
- Point make_point(long double x, long double y) {
- Point a;
- a.x = x; a.y = y;
- return a;
- }
- vector <vector <Point>> highways;
- vector <int> weights;
- Point office;
- int n, w;
- long double x, y;
- void optimize(Point cur) {
- cur.x = cur.x - office.x;
- cur.y = cur.y - office.y;
- }
- void read () {
- cin >> n >> w >> x >> y;
- office = make_point(x, y);
- highways.resize(n);
- weights.resize(n);
- for (int i = 0; i < n; ++i) {
- int k, p;
- cin >> k >> p;
- weights[i] = p;
- highways[i].resize(k);
- for (int j = 0; j < k; ++j) {
- long double xi, yi;
- cin >> xi >> yi;
- highways[i][j] = make_point(xi, yi);
- optimize(highways[i][j]);
- }
- }
- office = make_point(0, 0);
- }
- int total() {
- int ans = 0;
- for (int weight : weights) {
- ans += weight;
- }
- return ans;
- }
- long double sqr(long double a) {
- return a * a;
- }
- double to_office(Point a) {
- long double x = a.x;
- long double y = a.y;
- return x * x + y * y;
- }
- long double find_normal(Point a, Point b) {
- Point left = a;
- Point right = make_point(b.x + EPS, b.y + EPS);
- while (fabs(left.x - right.x) > EPS || fabs(left.y - right.y) > EPS) {
- Point m1 = make_point(left.x + (right.x - left.x) / 3, left.y + (right.y - left.y) / 3);
- Point m2 = make_point(right.x - (right.x - left.x) / 3, right.y - (right.y - left.y) / 3);
- if (to_office(m1) > to_office(m2)) {
- left.x = m1.x;
- left.y = m1.y;
- }
- else {
- right.x = m2.x;
- right.y = m2.y;
- }
- }
- return to_office(left);
- }
- long double find_optimal(int i) {
- long double answer = 1e9;
- for (int j = 0; j < (int)highways[i].size(); ++j) {
- long double to_point = to_office(highways[i][j]);
- answer = min(answer, to_point);
- }
- for (int j = 0; j < (int)highways[i].size() - 1; ++j) {
- Point a = highways[i][j];
- Point b = highways[i][j + 1];
- long double normal = find_normal(a, b);
- answer = min(answer, normal);
- }
- return sqrt(answer);
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- int t; cin >> t;
- for (int test = 0; test < t; ++test) {
- read();
- cout << total() << "\n";
- if (total() < w) {
- cout << "-1\n";
- continue;
- }
- vector <long double> optimals(n);
- for (int i = 0; i < n; ++i) {
- optimals[i] = find_optimal(i);
- }
- int max_weight = 0;
- for (int weight : weights) max_weight = max(max_weight, weight);
- long double dp[n + 1][w + max_weight + 1];
- for (int i = 0; i <= n; ++i) {
- for (int j = 0; j <= w + max_weight; ++j) {
- dp[i][j] = 1e9;
- }
- }
- dp[0][0] = 0;
- for (int i = 1; i <= n; ++i) {
- for (int j = 0; j <= w + max_weight; ++j) {
- dp[i][j] = dp[i - 1][j];
- }
- for (int j = 1; j <= w + max_weight; ++j) {
- if (j >= weights[i]) {
- if (dp[i - 1][j - weights[i - 1]] - 1e9 < EPS) {
- dp[i][j] = min(dp[i][j], dp[i - 1][j - weights[i - 1]] + optimals[i - 1]);
- }
- }
- }
- }
- long double out = 1e9;
- for (int i = w; i <= w + max_weight; ++i) {
- out = min(out, dp[n][i]);
- }
- cout << out << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement