Codeforces Round #319 Div1 C: Points on Plane
解法
縦,横1000の長方形に切る.
長方形内で点をyの値でソートする.ひとつの長方形内では,そこに含まれる点の数をPとすると,x軸方向に1000*P,y軸方向にの長さが最大で必要になる.長方形間ではx軸方向に最大で2000必要になり,これは1000個ある.
よって合計の長さは最大で,である.
コード
import java.io.IOException; import java.io.InputStream; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.NoSuchElementException; public class Main { private final int BUCKET_NUM = 1010;// バケットの横幅 public void solve() { FastScanner scanner = new FastScanner(); int N = scanner.nextInt(); ArrayList<ArrayList<Point>> points = new ArrayList<>(); for (int i = 0; i < BUCKET_NUM; i++) { points.add(new ArrayList<Point>()); } for (int i = 0; i < N; i++) { int x = scanner.nextInt(); int y = scanner.nextInt(); int bucket = x / BUCKET_NUM; points.get(bucket).add(new Point(i + 1, x, y)); } for (int i = 0; i < BUCKET_NUM; i++) { if (i % 2 == 0) { // 偶数番目の長方形なら昇順にソートする Collections.sort(points.get(i), new Comparator<Point>() { @Override public int compare(Point p1, Point p2) { if (p1.y == p2.y) { return p1.x - p2.x; } return p1.y - p2.y; } }); } else { // 奇数番目の長方形なら降順にソートする Collections.sort(points.get(i), new Comparator<Point>() { @Override public int compare(Point p1, Point p2) { if (p1.y == p2.y) { return p1.x - p2.x; } return p2.y - p1.y; } }); } } StringBuilder sb = new StringBuilder(); for (ArrayList<Point> arrayList : points) { for (Point point2 : arrayList) { sb.append(point2.id + " "); } } System.out.println(sb.toString()); } public static void main(String[] args) { new Main().solve(); } } class Point { int id, x, y; public Point(int id, int x, int y) { this.id = id; this.x = x; this.y = y; } } class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) { return true; } else { ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1; } private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; } private void skipUnprintable() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; } public boolean hasNext() { skipUnprintable(); return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public int nextInt() { return (int) nextLong(); } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while (true) { if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; } else if (b == -1 || !isPrintableChar(b)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } }