Submission #83876
Source Code Expand
import static java.lang.Math.*; import static java.util.Arrays.*; import java.util.*; import java.io.*; public class Main { final double EPS = 1e-10; int signum(double d) { return d < 0 ? -1 : d > 0 ? 1 : 0; } class P implements Comparable<P> { double x, y; int id; public P(double x, double y) { this.x = x; this.y = y; } public int compareTo(P o) { return x != o.x ? Double.compare(x, o.x) : Double.compare(y, o.y); } public String toString() { return "(" + x + "," + y + ")"; } public double abs() {return sqrt(x * x + y * y); } public double abs2() {return x * x + y * y; } public double arg() { return atan2(y, x); } public P mul(double k) {return new P(x * k, y * k);} public P div(double k) {return new P(x / k, y / k);} public P add(P o) {return new P(x + o.x, y + o.y);} public P sub(P o) {return new P(x - o.x, y - o.y);} public P mul(P o) {return new P(x * o.x - y * o.y, x * o.y + y * o.x); } public P div(P o) {return new P(x * o.x + y * o.y, -x * o.y + y * o.x).div(o.abs2()); } public double dot(P o) {return x * o.x + y * o.y;} // a b sin(t) public double det(P o) {return x * o.y - y * o.x;} // a b cos(t) public P normal() { return this.div(this.abs()); } public P rot90() { return new P(-y, x); } } final int OUT = 0; final int IN = 1; final int ON = 2; int containTP(P a, P b, P c, P p) { b = b.sub(a); c = c.sub(a); p = p.sub(a); double det = b.det(c); int sd = signum(det); if (sd == 0) return OUT; // 3角形が縮退してる double s = p.det(c); double t = b.det(p); if (sd == -1) {det = -det; s = -s; t = -t;} return (0 <= s && s <= det && 0 <= t && t <= det && s + t <= det) ? IN : OUT; } void solve() { int n = sc.nextInt(); P[] ps = new P[n]; for (int i = 0; i < n; i++) { ps[i] = new P(sc.nextDouble(), sc.nextDouble()); ps[i].id = i + 1; } sort(ps); if (n == 1) { double res = 0; res += abs(ps[0].x); out.printf("%.7f\n", res); return; } V[] vs = new V[2 * n + 2]; for (int i = 0; i < vs.length; i++) { vs[i] = new V(); } V s = vs[2 * n]; V t = vs[2 * n + 1]; for (int i = 0; i < n; i++) { s.add(vs[i], 1, 0); } for (int i = 0; i < n; i++) { vs[n + i].add(t, 1, 0); } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { double cost = getCost(ps[i].x, ps[i].y, ps[j].x, ps[j].y); // tr(cost, ps[i], ps[j]); vs[i].add(vs[n + j], 1, cost); } } double res = minCostMaxFlow(vs, s, t, n) / 2; out.printf("%.7f\n", res); return; } double getCost(double x1, double y1, double x2, double y2) { double res = abs(x1) + abs(x2); res = min(res, Math.hypot(x1 + x2, y1 - y2)); return res; } static final double INF = 1L << 18; double minCostMaxFlow(V[] vs, V s, V t, int flow) { double res = 0; while (flow > 0) { for (V v : vs) v.min = INF; PriorityQueue<E> que = new PriorityQueue<E>(); s.min = 0; que.offer(new E(s, 0, 0)); while (!que.isEmpty()) { E crt = que.poll(); if (Math.abs(crt.cost - crt.to.min) < EPS) { for (E e : crt.to.es) { double tmp = crt.cost + e.cost + crt.to.h - e.to.h; if (e.cap > 0 && e.to.min > tmp + EPS) { e.to.min = tmp; e.to.prev = e; que.offer(new E(e.to, 0, e.to.min)); } } } } if (t.min == INF / 2) return -1; int d = flow; for (E e = t.prev; e != null; e = e.rev.to.prev) { d = min (d, e.cap); } for (E e = t.prev; e != null; e = e.rev.to.prev) { res += d * e.cost; e.cap -= d; e.rev.cap += d; } flow -= d; for (V v : vs) v.h += v.min; } return res; } class V { int id; ArrayList<E> es = new ArrayList<E>(); E prev; double min, h; void add (V to, int cap, double cost) { E e = new E(to, cap, cost), rev = new E(this, 0, -cost); e.rev= rev; rev.rev = e; es.add(e); to.es.add(rev); } } class E implements Comparable<E> { V to; E rev; int cap; double cost; E (V to, int cap, double cost) { this.to = to; this.cap = cap; this.cost = cost; } public int compareTo(E o) { return signum(cost - o.cost); } } public static void main(String[] args) throws Exception { new Main().run(); } static void tr(Object... os) { System.err.println(deepToString(os)); } MyScanner sc = null; PrintWriter out = null; public void run() throws Exception { sc = new MyScanner(System.in); out = new PrintWriter(System.out); for (;sc.hasNext();) { solve(); out.flush(); } out.close(); } void print(int[] a) { out.print(a[0]); for (int i = 1; i < a.length; i++) out.print(" " + a[i]); out.println(); } class MyScanner { String line; BufferedReader reader; StringTokenizer tokenizer; public MyScanner(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream)); tokenizer = null; } public void eat() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { line = reader.readLine(); if (line == null) { tokenizer = null; return; } tokenizer = new StringTokenizer(line); } catch (IOException e) { throw new RuntimeException(e); } } } public String next() { eat(); return tokenizer.nextToken(); } public String nextLine() { try { return reader.readLine(); } catch (IOException e) { throw new RuntimeException(e); } } public boolean hasNext() { eat(); return (tokenizer != null && tokenizer.hasMoreElements()); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } public int[] nextIntArray(int n) { int[] a = new int[n]; for (int i = 0; i < n; i++) a[i] = nextInt(); return a; } } }
Submission Info
Submission Time | |
---|---|
Task | B - 玉座の間 |
User | hs484 |
Language | Java (OpenJDK 1.7.0) |
Score | 200 |
Code Size | 6117 Byte |
Status | AC |
Exec Time | 546 ms |
Memory | 30268 KB |
Judge Result
Set Name | Subtask1 | Subtask2 | Subtask3 | Subtask4 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 50 / 50 | 50 / 50 | 50 / 50 | 50 / 50 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Subtask1 | 11_rand00.txt, 11_rand01.txt, 11_rand02.txt, 11_rand03.txt, 11_rand04.txt, 11_rand05.txt, 11_rand06.txt, 11_rand07.txt, 11_rand08.txt, 11_rand09.txt, 11_rand10.txt, 11_rand11.txt, 11_rand12.txt, 11_rand13.txt, 11_rand14.txt, 11_rand15.txt, 11_rand16.txt, 11_rand17.txt, 11_rand18.txt, 11_rand19.txt, 11_rand20.txt, 11_rand21.txt, 11_rand22.txt, 11_rand23.txt, 11_rand24.txt |
Subtask2 | 11_rand00.txt, 11_rand01.txt, 11_rand02.txt, 11_rand03.txt, 11_rand04.txt, 11_rand05.txt, 11_rand06.txt, 11_rand07.txt, 11_rand08.txt, 11_rand09.txt, 11_rand10.txt, 11_rand11.txt, 11_rand12.txt, 11_rand13.txt, 11_rand14.txt, 11_rand15.txt, 11_rand16.txt, 11_rand17.txt, 11_rand18.txt, 11_rand19.txt, 11_rand20.txt, 11_rand21.txt, 11_rand22.txt, 11_rand23.txt, 11_rand24.txt, 21_rand00.txt, 21_rand01.txt, 21_rand02.txt, 21_rand03.txt, 21_rand04.txt, 21_rand05.txt, 21_rand06.txt, 21_rand07.txt, 21_rand08.txt, 21_rand09.txt, 21_rand10.txt, 21_rand11.txt, 21_rand12.txt, 21_rand13.txt, 21_rand14.txt, 21_rand15.txt, 21_rand16.txt, 21_rand17.txt, 21_rand18.txt, 21_rand19.txt, 21_rand20.txt, 21_rand21.txt, 21_rand22.txt, 21_rand23.txt, 21_rand24.txt |
Subtask3 | 11_rand00.txt, 11_rand01.txt, 11_rand02.txt, 11_rand03.txt, 11_rand04.txt, 11_rand05.txt, 11_rand06.txt, 11_rand07.txt, 11_rand08.txt, 11_rand09.txt, 11_rand10.txt, 11_rand11.txt, 11_rand12.txt, 11_rand13.txt, 11_rand14.txt, 11_rand15.txt, 11_rand16.txt, 11_rand17.txt, 11_rand18.txt, 11_rand19.txt, 11_rand20.txt, 11_rand21.txt, 11_rand22.txt, 11_rand23.txt, 11_rand24.txt, 21_rand00.txt, 21_rand01.txt, 21_rand02.txt, 21_rand03.txt, 21_rand04.txt, 21_rand05.txt, 21_rand06.txt, 21_rand07.txt, 21_rand08.txt, 21_rand09.txt, 21_rand10.txt, 21_rand11.txt, 21_rand12.txt, 21_rand13.txt, 21_rand14.txt, 21_rand15.txt, 21_rand16.txt, 21_rand17.txt, 21_rand18.txt, 21_rand19.txt, 21_rand20.txt, 21_rand21.txt, 21_rand22.txt, 21_rand23.txt, 21_rand24.txt, 31_rand00.txt, 31_rand01.txt, 31_rand02.txt, 31_rand03.txt, 31_rand04.txt, 31_rand05.txt, 31_rand06.txt, 31_rand07.txt, 31_rand08.txt, 31_rand09.txt, 31_rand10.txt, 31_rand11.txt, 31_rand12.txt, 31_rand13.txt, 31_rand14.txt, 31_rand15.txt, 31_rand16.txt, 31_rand17.txt, 31_rand18.txt, 31_rand19.txt, 31_rand20.txt, 31_rand21.txt, 31_rand22.txt, 31_rand23.txt, 31_rand24.txt |
Subtask4 | 11_rand00.txt, 11_rand01.txt, 11_rand02.txt, 11_rand03.txt, 11_rand04.txt, 11_rand05.txt, 11_rand06.txt, 11_rand07.txt, 11_rand08.txt, 11_rand09.txt, 11_rand10.txt, 11_rand11.txt, 11_rand12.txt, 11_rand13.txt, 11_rand14.txt, 11_rand15.txt, 11_rand16.txt, 11_rand17.txt, 11_rand18.txt, 11_rand19.txt, 11_rand20.txt, 11_rand21.txt, 11_rand22.txt, 11_rand23.txt, 11_rand24.txt, 21_rand00.txt, 21_rand01.txt, 21_rand02.txt, 21_rand03.txt, 21_rand04.txt, 21_rand05.txt, 21_rand06.txt, 21_rand07.txt, 21_rand08.txt, 21_rand09.txt, 21_rand10.txt, 21_rand11.txt, 21_rand12.txt, 21_rand13.txt, 21_rand14.txt, 21_rand15.txt, 21_rand16.txt, 21_rand17.txt, 21_rand18.txt, 21_rand19.txt, 21_rand20.txt, 21_rand21.txt, 21_rand22.txt, 21_rand23.txt, 21_rand24.txt, 31_rand00.txt, 31_rand01.txt, 31_rand02.txt, 31_rand03.txt, 31_rand04.txt, 31_rand05.txt, 31_rand06.txt, 31_rand07.txt, 31_rand08.txt, 31_rand09.txt, 31_rand10.txt, 31_rand11.txt, 31_rand12.txt, 31_rand13.txt, 31_rand14.txt, 31_rand15.txt, 31_rand16.txt, 31_rand17.txt, 31_rand18.txt, 31_rand19.txt, 31_rand20.txt, 31_rand21.txt, 31_rand22.txt, 31_rand23.txt, 31_rand24.txt, 41_rand00.txt, 41_rand01.txt, 41_rand02.txt, 41_rand03.txt, 41_rand04.txt, 41_rand05.txt, 41_rand06.txt, 41_rand07.txt, 41_rand08.txt, 41_rand09.txt, 41_rand10.txt, 41_rand11.txt, 41_rand12.txt, 41_rand13.txt, 41_rand14.txt, 41_rand15.txt, 41_rand16.txt, 41_rand17.txt, 41_rand18.txt, 41_rand19.txt, 41_rand20.txt, 41_rand21.txt, 41_rand22.txt, 41_rand23.txt, 41_rand24.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
11_rand00.txt | AC | 429 ms | 19508 KB |
11_rand01.txt | AC | 399 ms | 19548 KB |
11_rand02.txt | AC | 394 ms | 19556 KB |
11_rand03.txt | AC | 401 ms | 19632 KB |
11_rand04.txt | AC | 399 ms | 19632 KB |
11_rand05.txt | AC | 403 ms | 19508 KB |
11_rand06.txt | AC | 404 ms | 19540 KB |
11_rand07.txt | AC | 399 ms | 19504 KB |
11_rand08.txt | AC | 401 ms | 19576 KB |
11_rand09.txt | AC | 407 ms | 19500 KB |
11_rand10.txt | AC | 402 ms | 19496 KB |
11_rand11.txt | AC | 407 ms | 19500 KB |
11_rand12.txt | AC | 395 ms | 19492 KB |
11_rand13.txt | AC | 399 ms | 19676 KB |
11_rand14.txt | AC | 399 ms | 19520 KB |
11_rand15.txt | AC | 403 ms | 19488 KB |
11_rand16.txt | AC | 403 ms | 19620 KB |
11_rand17.txt | AC | 400 ms | 19564 KB |
11_rand18.txt | AC | 407 ms | 19512 KB |
11_rand19.txt | AC | 410 ms | 19508 KB |
11_rand20.txt | AC | 403 ms | 19508 KB |
11_rand21.txt | AC | 400 ms | 19508 KB |
11_rand22.txt | AC | 403 ms | 19500 KB |
11_rand23.txt | AC | 400 ms | 19612 KB |
11_rand24.txt | AC | 398 ms | 19512 KB |
21_rand00.txt | AC | 418 ms | 19752 KB |
21_rand01.txt | AC | 430 ms | 19820 KB |
21_rand02.txt | AC | 432 ms | 19740 KB |
21_rand03.txt | AC | 412 ms | 19760 KB |
21_rand04.txt | AC | 406 ms | 19728 KB |
21_rand05.txt | AC | 408 ms | 19748 KB |
21_rand06.txt | AC | 396 ms | 19508 KB |
21_rand07.txt | AC | 398 ms | 19760 KB |
21_rand08.txt | AC | 402 ms | 19800 KB |
21_rand09.txt | AC | 406 ms | 19748 KB |
21_rand10.txt | AC | 400 ms | 19748 KB |
21_rand11.txt | AC | 405 ms | 19748 KB |
21_rand12.txt | AC | 406 ms | 19740 KB |
21_rand13.txt | AC | 409 ms | 19760 KB |
21_rand14.txt | AC | 405 ms | 19892 KB |
21_rand15.txt | AC | 407 ms | 19688 KB |
21_rand16.txt | AC | 403 ms | 19684 KB |
21_rand17.txt | AC | 402 ms | 19804 KB |
21_rand18.txt | AC | 410 ms | 19752 KB |
21_rand19.txt | AC | 407 ms | 19740 KB |
21_rand20.txt | AC | 407 ms | 19808 KB |
21_rand21.txt | AC | 413 ms | 19764 KB |
21_rand22.txt | AC | 407 ms | 19756 KB |
21_rand23.txt | AC | 406 ms | 19756 KB |
21_rand24.txt | AC | 406 ms | 19808 KB |
31_rand00.txt | AC | 402 ms | 19756 KB |
31_rand01.txt | AC | 404 ms | 19772 KB |
31_rand02.txt | AC | 426 ms | 20916 KB |
31_rand03.txt | AC | 431 ms | 19768 KB |
31_rand04.txt | AC | 473 ms | 20712 KB |
31_rand05.txt | AC | 428 ms | 19812 KB |
31_rand06.txt | AC | 440 ms | 19804 KB |
31_rand07.txt | AC | 447 ms | 19764 KB |
31_rand08.txt | AC | 406 ms | 19760 KB |
31_rand09.txt | AC | 419 ms | 20712 KB |
31_rand10.txt | AC | 417 ms | 19800 KB |
31_rand11.txt | AC | 412 ms | 19768 KB |
31_rand12.txt | AC | 427 ms | 20844 KB |
31_rand13.txt | AC | 409 ms | 19768 KB |
31_rand14.txt | AC | 412 ms | 19760 KB |
31_rand15.txt | AC | 412 ms | 19768 KB |
31_rand16.txt | AC | 406 ms | 19764 KB |
31_rand17.txt | AC | 413 ms | 19892 KB |
31_rand18.txt | AC | 447 ms | 24296 KB |
31_rand19.txt | AC | 426 ms | 23208 KB |
31_rand20.txt | AC | 434 ms | 22824 KB |
31_rand21.txt | AC | 408 ms | 19760 KB |
31_rand22.txt | AC | 416 ms | 19884 KB |
31_rand23.txt | AC | 451 ms | 23628 KB |
31_rand24.txt | AC | 411 ms | 19764 KB |
41_rand00.txt | AC | 449 ms | 24816 KB |
41_rand01.txt | AC | 415 ms | 19752 KB |
41_rand02.txt | AC | 498 ms | 25596 KB |
41_rand03.txt | AC | 527 ms | 26112 KB |
41_rand04.txt | AC | 498 ms | 26908 KB |
41_rand05.txt | AC | 499 ms | 25424 KB |
41_rand06.txt | AC | 495 ms | 25528 KB |
41_rand07.txt | AC | 517 ms | 27816 KB |
41_rand08.txt | AC | 419 ms | 19764 KB |
41_rand09.txt | AC | 482 ms | 25344 KB |
41_rand10.txt | AC | 411 ms | 19752 KB |
41_rand11.txt | AC | 502 ms | 26832 KB |
41_rand12.txt | AC | 512 ms | 27924 KB |
41_rand13.txt | AC | 465 ms | 24612 KB |
41_rand14.txt | AC | 500 ms | 25608 KB |
41_rand15.txt | AC | 428 ms | 20784 KB |
41_rand16.txt | AC | 421 ms | 19776 KB |
41_rand17.txt | AC | 500 ms | 26444 KB |
41_rand18.txt | AC | 546 ms | 30268 KB |
41_rand19.txt | AC | 537 ms | 29556 KB |
41_rand20.txt | AC | 482 ms | 25448 KB |
41_rand21.txt | AC | 414 ms | 19688 KB |
41_rand22.txt | AC | 481 ms | 25304 KB |
41_rand23.txt | AC | 520 ms | 27976 KB |
41_rand24.txt | AC | 489 ms | 26744 KB |