fork download
copy 
  1. /**
  2.  * Created by Zlobober on 14.04.15.
  3.  */
  4. import java.io.*;
  5. import java.util.*;
  6.  
  7. public class TaskC {
  8.     private final InputReader reader;
  9.     private final OutputWriter writer;
  10.  
  11.     public TaskC(InputReader reader, OutputWriter writer) {
  12.         this.reader = reader;
  13.         this.writer = writer;
  14.     }
  15.  
  16.     public static void main(String[] args) {
  17.         InputReader reader = new InputReader(System.in);
  18.         OutputWriter writer = new OutputWriter(System.out);
  19.         new TaskC(reader, writer).run();
  20.         writer.writer.flush();
  21.     }
  22.  
  23.     int[] X, Y;
  24.  
  25.     class Pair implements Comparable<Pair> {
  26.         int x, y;
  27.         Pair(int x, int y) {
  28.             this.x = x;
  29.             this.y = y;
  30.         }
  31.         @Override
  32.         public int compareTo(Pair other) {
  33.             if (this.x != other.x)
  34.                 return Integer.compare(this.x, other.x);
  35.             return Integer.compare(this.y, other.y);
  36.         }
  37.     }
  38.  
  39.     List[] eq;
  40.     public void run() {
  41.         int n = reader.nextInt();
  42.         X = new int[n];
  43.         Y = new int[n];
  44.         TreeSet<Pair> used = new TreeSet<Pair>();
  45.         for (int i = 0; i < n; i++) {
  46.             X[i] = reader.nextInt();
  47.             Y[i] = reader.nextInt();
  48.         }
  49.         int apt = 0;
  50.         Integer[] A = new Integer[n];
  51.         for (int i = 0; i < n; i++) {
  52.             if (used.contains(new Pair(X[i], Y[i])))
  53.                 continue;
  54.             else {
  55.                 A[apt++] = i;
  56.                 used.add(new Pair(X[i], Y[i]));
  57.             }
  58.         }
  59.         A = Arrays.copyOf(A, apt);
  60.         int pos = 0;
  61.         int neg = 0;
  62.         for (int i = 1; i < A.length; i++) {
  63.             if (Y[A[i]] > Y[A[pos]] || (Y[A[i]] == Y[A[pos]] && X[A[i]] > X[A[pos]]))
  64.                 pos = i;
  65.             if (X[A[i]] > X[A[neg]] || (X[A[i]] == X[A[neg]] && Y[A[i]] > Y[A[neg]]))
  66.                 neg = i;
  67.         }
  68.         neg = A[neg];
  69.         int t = A[0];
  70.         A[0] = A[pos];
  71.         A[pos] = t;
  72.         pos = A[0];
  73.         final Integer[] finalA = A;
  74.         Arrays.sort(A, 1, A.length, new Comparator<Integer>() {
  75.             @Override
  76.             public int compare(Integer a, Integer b) {
  77.                 long v = vec(finalA[0], a, b);
  78.                 if (v != 0)
  79.                     return Long.compare(v, 0);
  80.                 else {
  81.                     int da = (X[a] - X[finalA[0]]) * (X[a] - X[finalA[0]]) + (Y[a] - Y[finalA[0]]) * (Y[a] - Y[finalA[0]]);
  82.                     int db = (X[b] - X[finalA[0]]) * (X[b] - X[finalA[0]]) + (Y[b] - Y[finalA[0]]) * (Y[b] - Y[finalA[0]]);
  83.                     return Long.compare(da, db);
  84.                 }
  85.             }
  86.         });
  87.         int[] H = new int[A.length];
  88.         int pt = 0;
  89.         H[pt++] = A[0];
  90.         if (pos != neg) {
  91.             for (int i = 1; i < A.length; i++) {
  92.                 int p = A[i];
  93.                 while (true) {
  94.                     if (pt < 2)
  95.                         break;
  96.                     int a = H[pt - 2];
  97.                     int b = H[pt - 1];
  98.                     long v = vec(a, b, p);
  99.                     if (v > 0)
  100.                         --pt;
  101.                     else
  102.                         break;
  103.                 }
  104.                 H[pt++] = p;
  105.                 if (p == neg)
  106.                     break;
  107.             }
  108.         }
  109.         Arrays.sort(H, 0, pt);
  110.         used.clear();
  111.         for (int i = 0; i < pt; i++)
  112.             used.add(new Pair(X[H[i]], Y[H[i]]));
  113.         for (int i = 0; i < n; i++)
  114.             if (used.contains(new Pair(X[i], Y[i])))
  115.                 writer.printf("%d ", i + 1);
  116.  
  117.         writer.printf("\n");
  118.     }
  119.  
  120.     long vec(int a, int b, int c) {
  121.         return 1l * X[c] * Y[a] * (X[b] - X[a]) * (Y[c] - Y[b]) - 1l * X[a] * Y[c] * (Y[b] - Y[a]) * (X[c] - X[b]);
  122.     }
  123.  
  124.  
  125.  
  126.     static class InputReader {
  127.         public BufferedReader reader;
  128.         public StringTokenizer tokenizer;
  129.  
  130.         public InputReader(InputStream stream) {
  131.             reader = new BufferedReader(new InputStreamReader(stream), 32768);
  132.             tokenizer = null;
  133.         }
  134.  
  135.         public String next() {
  136.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  137.                 try {
  138.                     tokenizer = new StringTokenizer(reader.readLine());
  139.                 } catch (IOException e) {
  140.                     throw new RuntimeException(e);
  141.                 }
  142.             }
  143.             return tokenizer.nextToken();
  144.         }
  145.  
  146.         public int nextInt() {
  147.             return Integer.parseInt(next());
  148.         }
  149.  
  150.         public double nextDouble() {
  151.             return Double.parseDouble(next());
  152.         }
  153.  
  154.         public long nextLong() {
  155.             return Long.parseLong(next());
  156.         }
  157.     }
  158.  
  159.     static class OutputWriter {
  160.         public PrintWriter writer;
  161.  
  162.         OutputWriter(OutputStream stream) {
  163.             writer = new PrintWriter(stream);
  164.         }
  165.  
  166.         public void printf(String format, Object... args) {
  167.             writer.print(String.format(Locale.ENGLISH, format, args));
  168.         }
  169.     }
  170. }
  171.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:7: error: class TaskC is public, should be declared in a file named TaskC.java
public class TaskC {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/mGeglg
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
secret

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!