Cod sursa(job #1047995)

Utilizator BarracudaFMI-Alex Dobrin Barracuda Data 5 decembrie 2013 02:49:49
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include<fstream>
#include<algorithm>
#include<cmath>
#define dim 1002
using namespace std;
 
ifstream f("patrate3.in");
ofstream g("patrate3.out");
double midx,midy,Dx,Dy;
int n,i,j,cnt;
typedef struct pnt{
    double x,y;
};
pnt v[dim],x2,x3;
int cmp(pnt a,pnt b){
    if(fabs(a.x-b.x)<0.0001)
        return a.y<b.y;
    return a.x<b.x;
}
int bs( pnt X  ) {
    int st,dr,mid;
    st=1;dr=n;
     
    while(  st<=dr   ) {
         
        mid=(st+dr)/2;
        if(fabs(X.x-v[mid].x)<0.0001 && fabs(X.y-v[mid].y)<0.0001) 
            return 1;
        if( cmp (X,v[mid]) )
            dr=mid-1;
        else
            st=mid+1;
         
    }
    return 0;
}
int main () {
     
    f>>n;
     
     
    for(i=1;i<=n;++i)
        f>>v[i].x>>v[i].y;
     
    sort(v+1,v+1+n,cmp);
    for(i=1;i<n;++i){
        for(j=i+1; j<=n;++j) {
             
            midx=(v[i].x+v[j].x)/2;
            midy=(v[i].y+v[j].y)/2;
            Dx=fabs(midx-v[i].x);
            Dy=fabs(midy-v[i].y);
             
            if(v[i].y<v[j].y) {
                 
                x2.x=midx+Dy;
                x2.y=midy-Dx;
                x3.x=midx-Dy;
                x3.y=midy+Dx;
                 
                if(bs(x2)&&bs(x3)) ++cnt;
            }
            else {
                x2.x=midx-Dy;
                x2.y=midy-Dx;
                x3.x=midx+Dy;
                x3.y=midy+Dx;
                 
                if(bs(x2)&&bs(x3)) ++cnt;
            }
        }
    }
    g<<cnt/2;
     
    return 0;
}