Cod sursa(job #1171770)

Utilizator hevelebalazshevele balazs hevelebalazs Data 16 aprilie 2014 12:44:50
Problema Triang Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define fr(i,a,b) for(i=a;i<b;++i)
#define N 1500
double x[N],y[N];
int I[N],n;
double eps=0.001;
int c(const void*a,const void*b){
    return x[*(int*)a]<x[*(int*)b]?-1:1;
    }
double dabs(double x){return x>0?x:-x;}
char find(int k,double X,double Y){
    int c,l=k+1,r=n-1;
    if(l>=n)return 0;
    while(l<r){
        c=(l+r)/2;
        if(dabs(x[I[c]]-X)<eps){l=c;break;}
        if(x[I[c]]<X) l=c+1;
        else r=c;
        }
    if(dabs(x[I[l]]-X)>=eps)return 0;
    r=l;
    while(l>k+1&&dabs(x[I[l-1]]-X)<eps)--l;
    while(r<n-1&&dabs(x[I[r+1]]-X)<eps)++r;
    ++r;
    fr(c,l,r) if(dabs(y[I[c]]-Y)<eps)return 1;
    return 0;
    }
/*char find(int k,double X,double Y){
    int i;
    fr(i,k++,n) if(dabs(x[I[i]]-X)<eps && dabs(y[I[i]]-Y) < eps)return 1;
    return 0;
    }*/
int main(){
    freopen("triang.in","r",stdin);
    freopen("triang.out","w",stdout);
    double s3=sqrt(3);
    int i,j;
    scanf("%i",&n);
    fr(i,0,n)scanf("%lf%lf",x+i,y+i);
    fr(i,0,n)I[i]=i;
    qsort(I,n,sizeof(*I),c);
    int s=0;
    fr(i,0,n){
        fr(j,i+1,n){
            double cx=(x[I[i]]+x[I[j]])/2;
            double cy=(y[I[i]]+y[I[j]])/2;
            double px=cx+s3*(y[I[i]]-cy);
            double py=cy-s3*(x[I[i]]-cx);
            s+=find(j,px,py);
            px=cx+s3*(y[I[j]]-cy);
            py=cy-s3*(x[I[j]]-cx);
            s+=find(j,px,py);
            }
        }
    printf("%i\n",s);
    return 0;
    }