JOI春合宿 2008-day3 Nightman
問題文 : 夜警
解法 :
登場する点のうち,
・警備員のいる点
・建物の点
を頂点としたグラフを作る. この際に, 建物の辺または対角線と交わっている時は辺を貼らないようにする.
これが出来れば, あとはダイクストラ法を各点に行うだけである.
コード :
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> using namespace std; typedef long long lint; struct Node { lint x, y; Node(lint x, lint y) : x(x), y(y) {} Node(){} }; struct Segment { int x1, y1, x2, y2; Segment(int x1, int y1, int x2, int y2) : x1(x1), y1(y1), x2(x2), y2(y2) {} Segment(){} }; struct Edge { int to; double cost; Edge(int to, double cost) : to(to), cost(cost){} Edge(){} }; bool operator > (const Edge &a, const Edge &b) { return (a.cost > b.cost); } vector<Node> v; vector<Segment> seg; vector<Edge> G[512]; bool cross(Node p1, Node p2, Node p3, Node p4) { bool judgeA = ((p1.x - p2.x) * (p3.y - p1.y) + (p1.y - p2.y) * (p1.x - p3.x)) * ((p1.x - p2.x) * (p4.y - p1.y) + (p1.y - p2.y) * (p1.x - p4.x)) < 0; bool judgeB = ((p3.x - p4.x) * (p1.y - p3.y) + (p3.y - p4.y) * (p3.x - p1.x)) * ((p3.x - p4.x) * (p2.y - p3.y) + (p3.y - p4.y) * (p3.x - p2.x)) < 0; return (judgeA && judgeB); } double dist(Node p, Node q) { return (sqrt((p.x - q.x) * (p.x - q.x) + (p.y - q.y) * (p.y - q.y))); } int a, b, c; int w, h; double dijkstra() { double dist[512]; for (int i = 0; i <= v.size(); i++) dist[i] = 999999999; priority_queue<Edge, vector<Edge>, greater<Edge> > pq; for (pq.push(Edge(v.size(), 0)); pq.size(); pq.pop()){ Edge x = pq.top(); if (0 <= x.to && x.to < a){ return (x.cost); } if (x.cost >= dist[x.to]) continue; dist[x.to] = x.cost; for (int i = 0; i < G[x.to].size(); i++){ Edge e = G[x.to][i]; pq.push(Edge(e.to, e.cost + x.cost)); } } return (999999999); } int main() { scanf("%d %d %d", &a, &b, &c); scanf("%d %d", &w, &h); int idx = 0; for (int i = 0; i < a; i++){ int x, y; scanf("%d %d", &x, &y); v.push_back(Node(x, y)); } for (int i = 0; i < b; i++){ int x1, y1, x2, y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2); v.push_back(Node(x1, y1)); v.push_back(Node(x2, y2)); v.push_back(Node(x1, y2)); v.push_back(Node(x2, y1)); seg.push_back(Segment(x1, y1, x2, y1)); seg.push_back(Segment(x1, y1, x1, y2)); seg.push_back(Segment(x2, y1, x2, y2)); seg.push_back(Segment(x1, y2, x2, y2)); seg.push_back(Segment(x1, y1, x2, y2)); seg.push_back(Segment(x1, y2, x2, y1)); } for (int i = 0; i < v.size(); i++){ for (int j = i + 1; j < v.size(); j++){ bool ok = true; for (int k = 0; k < seg.size(); k++){ if (cross(v[i], v[j], Node(seg[k].x1, seg[k].y1), Node(seg[k].x2, seg[k].y2))) ok = false; } if (ok){ G[i].push_back(Edge(j, dist(v[i], v[j]))); G[j].push_back(Edge(i, dist(v[i], v[j]))); } } } double sum = 0; for (int i = 0; i < c; i++){ Node t; G[v.size()].clear(); for (int j = 0; j < v.size(); j++){ if (G[j].size() && (G[j].end() - 1)->to == v.size()){ G[j].erase(G[j].end() - 1, G[j].end()); } } scanf("%lld %lld", &t.x, &t.y); for (int j = 0; j < v.size(); j++){ bool ok = true; for (int k = 0; k < seg.size(); k++){ if (cross(t, v[j], Node(seg[k].x1, seg[k].y1), Node(seg[k].x2, seg[k].y2))) ok = false; } if (ok){ G[j].push_back(Edge(v.size(), dist(v[j], t))); G[v.size()].push_back(Edge(j, dist(v[j], t))); } } sum += 2 * dijkstra(); } printf("%.3lf\n", sum); return (0); }