Cod sursa(job #131783)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 4 februarie 2008 14:38:13
Problema Patrate 3 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.97 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define prec 0.00001

long n,i,j,sol,ind[1002],ok,low,mid,high;
double x[1002],y[1002];
double dx,dy,mijx,mijy,x2,x3,y2,y3;

int comp1(const void * n1, const void *n2){
    return 10000*((double)y[*((long*)n1)]-y[*((long*)n2)]);
}
int comp2(const void * n1, const void *n2){
    return 10000*((double)x[*((long*)n1)]-x[*((long*)n2)]);
}

int main(){
    freopen("patrate3.in","r",stdin);
    freopen("patrate3.out","w",stdout);
    
    scanf("%ld",&n);
    for (i=1;i<=n;i++){
        scanf("%lf %lf",&x[i],&y[i]);
        ind[i]=i;
    }
    
    qsort(ind+1,n,sizeof(long),comp1);
    qsort(ind+1,n,sizeof(long),comp2);
    
    for (i=1;i<=n;i++)
        for (j=i+1;j<=n;j++){
            mijx=(double)(x[i]+x[j])/2;
            mijy=(double)(y[i]+y[j])/2;
            if (mijx>x[i])dx=mijx-x[i];
            else dx=x[i]-mijx;
            if (mijy>y[i])dy=mijy-y[i];
            else dy=y[i]-mijy;
            if (y[i]<y[j]){
               x2=mijx+dy;
               y2=mijy-dx;
               x3=mijx-dy;
               y3=mijy+dx;
            }
            else{
                x2=mijx-dy;
                y2=mijy+dx;
                x3=mijx+dy;
                y3=mijy-dx;
            }

            /*if (i==4&&j==6){
               printf("%f %f\n%f %f\n",x[i],y[i],x[j],y[j]);
               printf("%f %f\n%f %f\n\n",x2,y2,x3,y3);
            }*/
               
            ok=0;
            low = 1;
            high = n;
            while (low <= high) {
                  mid = (low + high) / 2;
                  if (x[ind[mid]]-x2>prec)
                     high = mid - 1;
                  else if (x2-x[ind[mid]]>prec)
                          low = mid + 1;
                       else
                           if (y[ind[mid]]-y2>prec)
                              high=mid-1;
                           else{
                               if (y2-y[ind[mid]]>prec)
                                  low=mid+1;
                               else
                                   {ok=1;break;}// found
                           }
            }
            if (ok){
            ok=0;
            low = 1;
            high = n;
            while (low <= high) {
                  mid = (low + high) / 2;
                  if (x[ind[mid]]-x3>prec)
                     high = mid - 1;
                  else if (x3-x[ind[mid]]>prec)
                          low = mid + 1;
                       else
                           if (y[ind[mid]]-y3>prec)
                              high=mid-1;
                           else{
                               if (y3-y[ind[mid]]>prec)
                                  low=mid+1;
                               else
                                   {ok=1;break;}// found
                           }
            }
            }
            if (ok)sol++;
        }
    printf("%ld\n",sol);

return 0;    
}