Cod sursa(job #601327)

Utilizator Smaug-Andrei C. Smaug- Data 5 iulie 2011 22:11:18
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define MAXN 1005
#define MAXA 501000
#define EPS 0.00000000000001
#define INF ((1<<31)-1)

int main(){

  freopen("trapez.in", "r", stdin);
  freopen("trapez.out", "w", stdout);

  int N, X[MAXN], Y[MAXN], i, j, cnt, res, sum;
  static double A[MAXA];

  scanf("%d", &N);
  for(i=1; i<=N; i++)
    scanf("%d%d", X+i, Y+i);

  cnt=0;
  for(i=1; i<=N; i++)
    for(j=i+1; j<=N; j++){
      if(X[i]==X[j])
	A[++cnt]=INF;
      else
	A[++cnt]=(double)(Y[j]-Y[i])/(double)(X[j]-X[i]);
    }

  sort(A+1, A+cnt+1);

  res=0; sum=0;
  for(i=2; i<=cnt; i++){
    if(A[i]-A[i-1] < EPS)
      sum++;
    else {
      res+=(sum*(sum+1))>>1;
      sum=0;
    }
  }

  printf("%d\n", res);

  return 0;

}