Cod sursa(job #1149333)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 21 martie 2014 18:25:57
Problema Patrate 3 Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
struct sp
{
double x,y;
}v[1005];
const double eps=1.e-14;
int n;
bool cmp(sp a1,sp b1)
{
       if(fabs(a1.x-b1.x)>=eps)
       return a1.x-b1.x<eps;
       return a1.y-b1.y<eps;
}
bool swag(double x,double y)
{
int st,dr,mi;
st=1;
dr=n;
while(st<=dr)
{
       mi=(st+dr)/2;
       if((fabs(x-v[mi].x))<eps && (fabs(y-v[mi].y))<eps)
       break;
       if((x-v[mi].x<-eps) || ((fabs(x-v[mi].x))<eps && (y-v[mi].y<-eps)))
              dr=mi-1;
              else
                     st=mi+1;
}
return st<=dr;
}
int main()
{
    freopen("patrate3.in","r",stdin);
    freopen("patrate3.out","w",stdout);
int i,j,nr=0;
double x3,y3,x4,y4,d,x2,y2,x1,y1;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf%lf",&v[i].x,&v[i].y);
sort(v+1,v+n+1,cmp);
for(i=1;i<=n;i++)
for(j=1;j<i;j++)
{
       x1=v[j].x;
       x2=v[i].x;
       y1=v[j].y;
       y2=v[i].y;
      d=fabs((x2-x1)-(y2-y1))/2;
      x3=x2-d;
      x4=x1+d;
      if(y1-y2>=eps)
      {
      y3=y1-d;
      y4=y2+d;
      }
      else
      {
             y3=y2-d;
             y4=y1+d;
      }
      if(swag(x3,y3),swag(x4,y4))
      nr++;
}
printf("%d\n",nr);
    return 0;
}