fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class TaskE_n2log {
  5.     private final InputReader reader;
  6.     private final OutputWriter writer;
  7.  
  8.     public TaskE_n2log(InputReader reader, OutputWriter writer) {
  9.         this.reader = reader;
  10.         this.writer = writer;
  11.     }
  12.  
  13.     public static void main(String[] args) {
  14.         InputReader reader = new InputReader(System.in);
  15.         OutputWriter writer = new OutputWriter(System.out);
  16.         new TaskE_n2log(reader, writer).run();
  17.         writer.writer.flush();
  18.     }
  19.  
  20.     int[][] gcd;
  21.  
  22.     int mygcd(int a, int b) {
  23.         return gcd[Math.abs(a)][Math.abs(b)];
  24.     }
  25.  
  26.     public void run() {
  27.         int n = reader.nextInt();
  28.         int ans = (int) (n * (n - 1) * 1l * (n - 2) / 6);
  29.         gcd = new int[201][201];
  30.         gcd[0][0] = 0;
  31.         for (int i = 0; i <= 200; i++) {
  32.             gcd[i][i] = i;
  33.             for (int j = 0; j < i; j++)
  34.                 gcd[j][i] = gcd[i][j] = (j == 0) ? i : gcd[j][i % j];
  35.         }
  36.         int[] X = new int[n], Y = new int[n];
  37.         for (int i = 0; i < n; i++) {
  38.             X[i] = reader.nextInt();
  39.             Y[i] = reader.nextInt();
  40.         }
  41.         long[] H = new long[n * (n - 1) / 2];
  42.         int hpt = 0;
  43.         for (int i = 0; i < n; i++) {
  44.             for (int j = 0; j < i; j++) {
  45.                 int A = Y[i] - Y[j], B = -X[i] + X[j];
  46.                 int C = A * X[i] + B * Y[i];
  47.                 int g = mygcd(A, B);
  48.                 A /= g;
  49.                 B /= g;
  50.                 C /= g;
  51.                 if (A < 0 || (A == 0 && B < 0)) {
  52.                     A = -A;
  53.                     B = -B;
  54.                     C = -C;
  55.                 }
  56.                 long hsh = C * 500 * 1l * 500 + (A + 250) * 500 + B;
  57.                 H[hpt++] = hsh;
  58.             }
  59.         }
  60.         Arrays.sort(H);
  61.  
  62.         int[] cnt = new int[n * n];
  63.         Arrays.fill(cnt, -1);
  64.         for (int i = 2; i <= n; i++)
  65.             cnt[i * (i - 1) / 2] = i;
  66.  
  67.         for (int l = 0, r = 0; l < H.length; l = r) {
  68.             while (r != H.length && H[l] == H[r])
  69.                 r++;
  70.             int q = r - l;
  71.             int v = cnt[r - l];
  72.             ans -= v * (v - 1) * 1l * (v - 2) / 6;
  73.         }
  74.         writer.printf("%d\n", ans);
  75.     }
  76.  
  77.  
  78.     static class InputReader {
  79.         public BufferedReader reader;
  80.         public StringTokenizer tokenizer;
  81.  
  82.         public InputReader(InputStream stream) {
  83.             reader = new BufferedReader(new InputStreamReader(stream), 32768);
  84.             tokenizer = null;
  85.         }
  86.  
  87.         public String next() {
  88.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  89.                 try {
  90.                     tokenizer = new StringTokenizer(reader.readLine());
  91.                 } catch (IOException e) {
  92.                     throw new RuntimeException(e);
  93.                 }
  94.             }
  95.             return tokenizer.nextToken();
  96.         }
  97.  
  98.         public int nextInt() {
  99.             return Integer.parseInt(next());
  100.         }
  101.  
  102.         public double nextDouble() {
  103.             return Double.parseDouble(next());
  104.         }
  105.  
  106.         public long nextLong() {
  107.             return Long.parseLong(next());
  108.         }
  109.     }
  110.  
  111.     static class OutputWriter {
  112.         public PrintWriter writer;
  113.  
  114.         OutputWriter(OutputStream stream) {
  115.             writer = new PrintWriter(stream);
  116.         }
  117.  
  118.         public void printf(String format, Object... args) {
  119.             writer.print(String.format(Locale.ENGLISH, format, args));
  120.         }
  121.     }
  122. }
  123.  
  124.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:4: error: class TaskE_n2log is public, should be declared in a file named TaskE_n2log.java
public class TaskE_n2log {
       ^
1 error
stdout
copy 
Standard output is empty
https://ideone.com/tdalVu
language:
Java (12.0.1)
created:
8 years ago
visibility:
public

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!