Cod sursa(job #176947)

Utilizator Mishu91Andrei Misarca Mishu91 Data 11 aprilie 2008 23:40:02
Problema Trapez Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 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)
   {
     return ((a.it * b.at) < (a.at * b.it));   
   }

};

int n, viz[Nmax*Nmax];;

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
      {
        p[nrp].it = INF;
        p[nrp++].at = 1;
      }
    }
      
  
  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());
      
for(int i=0; i<nrp; i++)
    printf("%d/%d\n",p[i].it,p[i].at);
  
  for(int i=1; i<nrp; i++)
    if(p[i].it * p[i-1].at == p[i].at * p[i-1].it)
     {  
      viz[i] += (viz[i-1] + 1);  
      nrtrap += viz[i];  
     }   
     
  printf("%d\n",nrtrap);   
  
  return 0;
}