Cod sursa(job #681346)

Utilizator ion824Ion Ureche ion824 Data 16 februarie 2012 22:34:48
Problema Patrate 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.59 kb
#include<cstdio>
#include<cmath>
#include<algorithm>
typedef struct { int x,y; }punct;
punct a[1004];
const int inm=10000;
bool compare(punct b,punct a){ if(a.x>b.x)return 1; else if(a.x==b.x && a.y>b.y)return 1; else return 0; }

int main(void){
    freopen ("patrate3.in","r",stdin);
    freopen ("patrate3.out","w",stdout);
    int i,n,v,u,x2,y2,x3,y3,dx,dy,mx,my,i1,j1,mij,j,nr=0; 
    scanf("%d\n",&n);
    for(i=1;i<=n;++i){
                      scanf("%d.%d",&v,&u);
                      if(v<0)a[i].x=(v*inm)-u;
                        else a[i].x=(v*inm)+u;  
                                       
                      scanf(" %d.%d\n",&v,&u);
                      if(v<0)a[i].y=(v*inm)-u;
                        else a[i].y=(v*inm)+u;
                      }
    std::sort(a+1,a+n+1,compare);                
    
    for(i=1;i<=n;++i)
      for(j=i+1;j<=n;++j)
            if(a[i].y<a[j].y){
                           mx=(a[i].x+a[j].x)/2;
                           my=(a[i].y+a[j].y)/2;
                           dx=abs(mx-a[i].x);
                           dy=abs(my-a[i].y);
                           x2=mx+dy; y2=my-dx;   
                           x3=mx-dy; y3=my+dx; 
                           i1=1; j1=n; 
                           while(j1-i1>1){
                                   mij=i1+(j1-i1)/2;
                                    if(a[mij].x<x2)i1=mij;
                                      else j1=mij;
                                          }
                          if(j1<=n)                
                          if(a[j1].x==x2 && a[j1].y==y2){
                                  i1=1; j1=n; 
                                  while(j1-i1>1){
                                         mij=i1+(j1-i1)/2;
                                          if(a[mij].x<x3)i1=mij;
                                            else j1=mij;
                                          }     
                                   if(a[j1].x==x3 && a[j1].y==y3)++nr;                                          
                                       }                                                                         
                              }
                     else
                        {
                         mx=(a[i].x+a[j].x)/2;
                         my=(a[i].y+a[j].y)/2;     
                         dx=abs(mx-a[i].x);
                         dy=abs(my-a[i].y);
                         x2=mx-dy; y2=my-dx;   
                         x3=mx+dy; y3=my+dx;      
                         while(j1-i1>1){
                                   mij=i1+(j1-i1)/2;
                                    if(a[mij].x<x2)i1=mij;
                                      else j1=mij;
                                          }  
                         if(j1<=n)                 
                         if(a[j1].x==x2 && a[j1].y==y2){
                                  i1=1; j1=n; 
                                  while(j1-i1>1){
                                         mij=i1+(j1-i1)/2;
                                          if(a[mij].x<x3)i1=mij;
                                            else j1=mij;
                                          }     
                                   if(a[j1].x==x3 && a[j1].y==y3)++nr;                                           
                                       }                    
                        }                                                                                                    
    printf("%d",nr);
    //for(i=1;i<=n;++i)printf("%d %d\n",a[i].x,a[i].y);
    return 0;
}