Cod sursa(job #230384)

Utilizator katakunaCazacu Alexandru katakuna Data 13 decembrie 2008 20:05:53
Problema Trapez Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

struct trapez{int x,y;} v[1011],a[1000001],b[1000001];
int x,rez,ox,oy,i,j,n,A,B,x1,x2,y1,y2;

int egal(trapez a,trapez b){

  if( (long long)a.y*(long long)b.x == (long long)b.y*(long long)a.x )
  return 1;

return 0;
}

int cmp(trapez a,trapez b){
return  (long long)a.y*(long long)b.x < (long long)b.y*(long long)a.x;
}

int main(){

FILE *f=fopen("trapez.in","r");
fscanf(f,"%d",&n);

   for(i=1;i<=n;i++){
   fscanf(f,"%d %d",&v[i].x,&v[i].y);
   }

fclose(f);

   for(i=1;i<=n;i++){
   x1=v[i].x;
   y1=v[i].y;
     for(j=i+1;j<=n;j++){
     x2=v[j].x;
     y2=v[j].y;

        if(y1==y2){
        oy++;
        }

        else{
         if(x1==x2){
         ox++;
         }
         else{
           if( (y1<y2 && x1>x2) || (y1>y2 && x1<x2) ){
           A++;
           a[A].x=x1-x2;
             if(a[A].x < 0)
             a[A].x*=-1;

           a[A].y=y1-y2;
             if(a[A].y < 0)
             a[A].y*=-1;
           }

           else{
           B++;
           b[B].x=x1-x2;
             if(b[B].x < 0)
             b[B].x*=-1;

           b[B].y=y1-y2;
             if(b[B].y < 0)
             b[B].y*=-1;
           }

         }
        }
     }
   }

sort(a+1,a+A+1,cmp);
sort(b+1,b+B+1,cmp);

rez=oy*(oy-1)/2;
rez+=ox*(ox-1)/2;
b[0].y=a[0].y=1;
x=1;

  for(i=1;i<=A;i++){
    if(!egal(a[i-1],a[i])){
    rez+=x*(x-1)/2;
    x=1;
    }
    else
    x++;
  }

x=1;

  for(i=1;i<=B;i++){
    if(!egal(b[i-1],b[i])){
    rez+=x*(x-1)/2;
    x=1;
    }
    else
    x++;
  }


FILE *g=fopen("trapez.out","w");
fprintf(f,"%d",rez);
fclose(g);

return 0;
}