Cod sursa(job #170550)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 2 aprilie 2008 21:32:36
Problema Triang Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <cstdio>
#include <math.h>
const double cos60=0.5;
const double sin60=0.86602540378443864676372317075294;
const double delta=0.001;
int n,nr;
double x[1501],y[1501];
double dabs(double x){
       return (x>=0?x:-x);
       }
int egal (double a,double b){
    return (dabs(a-b)<delta?1:0);
    }
void qsort(int ls,int ld){
     int i=ls,j=ld,mij=(ls+ld)/2;
     do {while (x[i]<x[mij] || (egal(x[i],x[mij]) && y[i]<y[mij])) i++;
         while (x[j]>x[mij] || (egal(x[j],x[mij]) && y[j]>y[mij])) j--;
         if (i<=j) {double aux=x[i];x[i]=x[j];x[j]=aux;
                    aux=y[i];y[i]=y[j];y[j]=aux;
                    i++;j--;}
         }
       while (i<=j);
     if (j>ls) qsort(ls,j);
     if (i<ld) qsort(i,ld);
     }
int gasit(int ls,int ld,double xx,double yy){
    int lo=ls,hi=ld,mij;
    while (lo<=hi) {
          mij=(lo+hi)/2;
          if (egal(x[mij],xx) && egal(y[mij],yy)) return 1;
          if (x[mij]>xx || (egal(x[mij],xx) && y[mij]>yy)) hi=mij-1;
          if (x[mij]<xx || (egal(x[mij],xx) && y[mij]<yy)) lo=mij+1;
          }
    return 0;
    }
int main(){
    int i,j;
    double xx,yy;
    freopen("triang.in","r",stdin);
    freopen("triang.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;i++) scanf("%lf %lf",&x[i],&y[i]);
    qsort(1,n);
    nr=0;
    for (i=1;i<=n-1;i++) 
      for (j=i+1;j<=n;j++)
       {xx=x[i]+cos60*(x[j]-x[i])+sin60*(y[i]-y[j]);
        yy=y[i]+cos60*(y[j]-y[i])-sin60*(x[i]-x[j]);
        if (gasit(1,n,xx,yy)) nr++;
        xx=x[j]+cos60*(x[i]-x[j])-sin60*(y[i]-y[j]);
        yy=y[j]+cos60*(y[i]-y[j])+sin60*(x[i]-x[j]);
        if (gasit(1,n,xx,yy)) nr++;
        }
    printf("%d",nr/3);
   }