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
AC × 25
AC × 50
AC × 75
AC × 100
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