Cod sursa(job #366213)

Utilizator mlazariLazari Mihai mlazari Data 21 noiembrie 2009 11:10:11
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

#define NMAX 1003
#define PMAX NMAX*(NMAX+1)/2

struct fraction {
  long long a,b; // a/b

  bool operator < (const fraction &f) const {
    if(!b) return false;
    if(!f.b) return true;
    if(b<0 && f.b<0 || b>0 && f.b>0) return a*f.b<b*f.a;
    else return a*f.b>b*f.a;
  }

  bool operator == (const fraction &f) const {
    return a*f.b==b*f.a;
  }
};

int n,i,j,result,nr=1;
int x[NMAX],y[NMAX];
vector<fraction> p;
vector<fraction>::iterator pr,c;

fraction make_fraction(int a,int b) {
  fraction f;
  f.a=a;
  f.b=b;
  return f;
}

int main() {
  freopen("trapez.in","r",stdin);
  freopen("trapez.out","w",stdout);
  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d%d",x+i,y+i);

  for(i=0;i<n-1;i++)
   for(j=i+1;j<n;j++)
    if(y[i]>y[j]) p.push_back(make_fraction(x[i]-x[j],y[i]-y[j]));
    else
     if(y[i]<y[j]) p.push_back(make_fraction(x[j]-x[i],y[j]-y[i]));
      else p.push_back(make_fraction(x[i]>x[j]?x[i]-x[j]:x[j]-x[i],0));

  sort(p.begin(),p.end());

  c=pr=p.begin();
  c++;
  while(c!=p.end()) {
    if(*c==*pr) nr++;
    else {
      result+=nr*(nr-1)/2;
      nr=1;
    }
    pr=c;
    c++;
  }
  if(nr>1) result+=nr*(nr-1)/2;

  printf("%d\n",result);
  return 0;
}