fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ldb = long double;
  4.  
  5. struct Point { ldb x, y; };
  6. struct Vec { ldb x, y; };
  7. struct Line { ldb a, b, c; };
  8.  
  9. const ldb EPS = 1e-12;
  10. const ldb FAR_COORD = 1e12L;
  11.  
  12. Vec vecto(const Point &A, const Point &B) { return {B.x - A.x, B.y - A.y}; }
  13. ldb cross(const Vec &A, const Vec &B) { return A.x * B.y - A.y * B.x; }
  14.  
  15. bool onseg(const Point &A, const Point &B, const Point &P) {
  16.     return (min(A.x, B.x) - 1e-15 <= P.x && P.x <= max(A.x, B.x) + 1e-15 &&
  17.             min(A.y, B.y) - 1e-15 <= P.y && P.y <= max(A.y, B.y) + 1e-15);
  18. }
  19.  
  20. Line make_line(const Point &A, const Point &B) {
  21.     Line r;
  22.     r.a = B.y - A.y;
  23.     r.b = A.x - B.x;
  24.     r.c = -r.a * A.x - r.b * A.y;
  25.     return r;
  26. }
  27.  
  28. bool seg_intersect(const Point &A, const Point &B, const Point &C, const Point &D) {
  29.     Line L1 = make_line(A, B);
  30.     Line L2 = make_line(C, D);
  31.     ldb det = L1.a * L2.b - L2.a * L1.b;
  32.     if (fabsl(det) < EPS) {
  33.         // parallel; check colinear + overlap
  34.         if (fabsl(L1.a * C.x + L1.b * C.y + L1.c) < 1e-9) {
  35.             if (onseg(A, B, C) || onseg(A, B, D) || onseg(C, D, A) || onseg(C, D, B)) return true;
  36.         }
  37.         return false;
  38.     }
  39.     ldb x = (L2.c * L1.b - L1.c * L2.b) / det;
  40.     ldb y = (L1.c * L2.a - L2.c * L1.a) / det;
  41.     Point P = {x, y};
  42.     return onseg(A, B, P) && onseg(C, D, P);
  43. }
  44.  
  45. bool point_in_polygon(const Point &pt, const vector<Point> &poly) {
  46.     int n = (int)poly.size();
  47.     // ray to a far point
  48.     Point farp = { FAR_COORD, FAR_COORD + 12345.0L };
  49.     int cnt = 0;
  50.     bool onboundary = false;
  51.     for (int i = 0; i < n; ++i) {
  52.         int j = (i + 1) % n;
  53.         Point A = poly[i], B = poly[j];
  54.         // check if point is on edge
  55.         ldb cr = cross(vecto(A, B), vecto(A, pt));
  56.         if (fabsl(cr) < 1e-12 && onseg(A, B, pt)) { onboundary = true; break; }
  57.         if (seg_intersect(A, B, pt, farp)) ++cnt;
  58.     }
  59.     if (onboundary) return true;
  60.     return (cnt % 2 == 1);
  61. }
  62.  
  63. ldb euclid_dist(const Point &A, const Point &B) {
  64.     ldb dx = A.x - B.x, dy = A.y - B.y;
  65.     return sqrt((double)(dx*dx + dy*dy));
  66. }
  67.  
  68. ldb trans_prob(const Point &A, const Point &B) {
  69.     ldb D = euclid_dist(A, B);
  70.     if (D > 1000.0L) D = 1000.0L;
  71.     return 1.0L - D / 1000.0L;
  72. }
  73.  
  74. int main() {
  75.     ios::sync_with_stdio(false);
  76.     cin.tie(nullptr);
  77.     int T; 
  78.     if (!(cin >> T)) return 0;
  79.     while (T--) {
  80.         int N, M;
  81.         cin >> N >> M;
  82.         vector<vector<Point>> layer(N);
  83.         for (int i = 0; i < N; ++i) {
  84.             int A; cin >> A;
  85.             layer[i].resize(A);
  86.             for (int j = 0; j < A; ++j) cin >> layer[i][j].x >> layer[i][j].y;
  87.         }
  88.         vector<Point> players(M);
  89.         for (int i = 0; i < M; ++i) cin >> players[i].x >> players[i].y;
  90.  
  91.         // vec[k] = list of player indices in layer k (0 = innermost)
  92.         vector<vector<int>> vec(N);
  93.         vector<int> which_layer(M, -1);
  94.  
  95.         for (int i = 0; i < M; ++i) {
  96.             int pos = -1;
  97.             // find smallest k such that player is inside layer[k]; because layers nested from 0..N-1 (inner->outer)
  98.             for (int k = 0; k < N; ++k) {
  99.                 if (point_in_polygon(players[i], layer[k])) {
  100.                     pos = k;
  101.                     break;
  102.                 }
  103.             }
  104.             if (pos == -1) {
  105.                 // If not inside any polygon, it must be outside all (i.e., beyond outermost)
  106.                 pos = N; // outside all; but per statement every player is not on walls, and there is at least one outside outermost
  107.             }
  108.             which_layer[i] = pos;
  109.             if (pos >= 0 && pos < N) vec[pos].push_back(i);
  110.             // If pos==N (outside all), we can treat them as layer N (outside). But in the problem players outside outermost are considered "outside".
  111.             // To simplify, we'll put those with pos==N into a separate vector index N-1? Actually problem states there is at least one player outside outermost:
  112.             // We'll handle transmissions from layer N-1 to outside group: so we need container for outside players:
  113.         }
  114.  
  115.         // Build list for outside (outside of layer N-1). Let's collect indices with which_layer == N separately.
  116.         vector<int> outside_players;
  117.         for (int i = 0; i < M; ++i) if (which_layer[i] == N) outside_players.push_back(i);
  118.  
  119.         // We will allow transmissions:
  120.         // from vec[k] -> vec[k+1] for k = 0..N-2
  121.         // from vec[N-1] -> outside_players
  122.         // find the unique player in innermost (layer 0) (problem guarantees exactly one)
  123.         int start = -1;
  124.         if (!vec[0].empty()) {
  125.             // problem guarantees exactly one player inside the innermost
  126.             start = vec[0][0];
  127.         } else {
  128.             // defensive: if none found, pick any with which_layer==0 (shouldn't happen)
  129.             for (int i = 0; i < M; ++i) if (which_layer[i] == 0) { start = i; break; }
  130.         }
  131.  
  132.         // multiplicative Dijkstra (maximize product of probabilities)
  133.         vector<ldb> prob(M, -1.0L);
  134.         if (start == -1) {
  135.             // no start found - but per statement shouldn't happen
  136.             cout << 0 << '\n';
  137.             continue;
  138.         }
  139.         prob[start] = 1.0L;
  140.         priority_queue<pair<ldb,int>> pq; // max-heap by first
  141.         pq.push({prob[start], start});
  142.  
  143.         auto relax_edge = [&](int u, int v) {
  144.             ldb w = trans_prob(players[u], players[v]);
  145.             ldb cand = prob[u] * w;
  146.             if (cand > prob[v] + 1e-15L) {
  147.                 prob[v] = cand;
  148.                 pq.push({prob[v], v});
  149.             }
  150.         };
  151.  
  152.         while (!pq.empty()) {
  153.             auto cur = pq.top(); pq.pop();
  154.             ldb curp = cur.first;
  155.             int u = cur.second;
  156.             if (curp + 1e-15L < prob[u]) continue; // stale
  157.             int layer_u = which_layer[u];
  158.             if (layer_u >= 0 && layer_u <= N-2) {
  159.                 // edges to next layer's players
  160.                 for (int v : vec[layer_u + 1]) relax_edge(u, v);
  161.             } else if (layer_u == N-1) {
  162.                 // edges to outside players
  163.                 for (int v : outside_players) relax_edge(u, v);
  164.             }
  165.             // if point is already outside (which_layer == N), no further edges
  166.         }
  167.  
  168.         // answer = max prob among players that are outside the outermost
  169.         ldb best = 0.0L;
  170.         if (!outside_players.empty()) {
  171.             for (int v : outside_players) best = max(best, prob[v]);
  172.         } else {
  173.             // maybe the "outside" players were placed into vec[N-1]? but per above we separated.
  174.             // Another possibility: players in layer N-1 are considered "outside outermost"? No.
  175.             // If no explicit outside players, maybe some players lie exactly outside but we didn't detect => fallback: consider any player in layer N-1 with no further layer as "outside"
  176.             for (int i = 0; i < M; ++i) if (which_layer[i] == N-1) best = max(best, prob[i]);
  177.         }
  178.  
  179.         // output floor(best * 1000)
  180.         long long outv = (long long) floor((double)(best * 1000.0L + 1e-12));
  181.         cout << outv << '\n';
  182.     }
  183.     return 0;
  184. }
  185.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/03Hym8
language:
C++14 (gcc 8.3)
created:
16 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!