Cod sursa(job #176953)

Utilizator Mishu91Andrei Misarca Mishu91 Data 12 aprilie 2008 00:02:13
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <cstdio>
#include <algorithm>

#define Nmax 1001
const long INF  = 1000000000;

using namespace std;

struct trap{long long x,y;} v[Nmax];

struct frac{long long it,at;} p[Nmax*Nmax];

int nrp;

struct cmp{
   bool operator ()(const frac &a, const frac &b)
   {
     long long x1,x2;
     x1 = (long long )(a.it * b.at);
     x2 = (long long )(a.at * b.it);
     return (x1 < x2);   
   }

};

int n, viz[Nmax*Nmax],nrinf;

int main()
{
  freopen("trapez.in","r",stdin);
  freopen("trapez.out","w",stdout);
  
  scanf("%d",&n);
  
  for(int i=0; i<n; i++)
    scanf("%lld %lld",&v[i].x,&v[i].y);
    
  for(int i=0; i<n-1; i++)
    for(int j=i+1; j<n; j++)
    {
      if(v[i].y != v[j].y)
      {
        p[nrp].it = v[i].x - v[j].x;
        p[nrp].at = v[i].y - v[j].y;
        if(p[nrp].at < 0)
          {
            p[nrp].it = -(p[nrp].it);
            p[nrp].at = -(p[nrp].at);
          }
          
        nrp++;
      }
      
      else
      nrinf++;
    }
      
  
  int nrtrap = 0;
  
  /*for(int i=0; i<nrp-1; i++)
    for(int j=i+1; j<nrp; j++)
      if(p[i].it * p[j].at == p[i].at * p[j].it)
        nrtrap ++;*/
        
  
  
  sort(p,p+nrp,cmp());

nrtrap = nrinf*(nrinf-1)/2;
/*for(int i=0; i<nrp; i++)
    printf("%d/%d\n",p[i].it,p[i].at)*/
  
  long long x1,x2;
  
  for(int i=1; i<nrp; i++)
  {
    x1 = (long long )(p[i].it * p[i-1].at);
    x2 = (long long )(p[i].at * p[i-1].it);
    if(x1 == x2)
     {  
      viz[i] = (viz[i-1] + 1);  
      nrtrap += viz[i];  
     }   
  }  
  printf("%d\n",nrtrap);   
  
  return 0;
}