Cod sursa(job #1171759)

Utilizator hevelebalazshevele balazs hevelebalazs Data 16 aprilie 2014 12:31:04
Problema Triang Scor 50
Compilator c Status done
Runda Arhiva de probleme Marime 1.46 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(x[I[c]]<X+eps) l=c+1;
        else r=c;
        }
    r=l;
    while(dabs(x[I[l]]-X)<eps)if(--l<0){l=0;break;};
    while(dabs(x[I[r]]-X)<eps)if(++r==n){r=n-1;break;};
    ++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;
    }