Cod sursa(job #1926722)

Utilizator tgm000Tudor Mocioi tgm000 Data 14 martie 2017 17:15:40
Problema Patrate 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include<cstdio>
#include<algorithm>
using namespace std;
struct punct{double x,y;};
punct v[1001];
bool eps(double x,double y){
   if(y-x>=1e-9)
      return -1;
   else if(x-y>=1e-9)
      return 1;
   else
      return 0;
}
bool cmp(punct a,punct b){
   int nr=eps(a.y,b.y);
   if(a.y<b.y)
      return true;
   else if(a.y>b.y)
      return false;
   else if(a.x<=b.x)
      return true;
   else
      return false;
}
bool findt(punct a,int n){
   int st=1,dr=n,poz,m;
   poz=n;
   while(st<=dr){
      m=(st+dr)/2;
      if(cmp(a,v[m])){
         dr=m-1;
         poz=m;
      }else
         st=m+1;
   }
   if(eps(a.x,v[poz].x)==0&&eps(a.y,v[poz].y)==0)
      return true;
   else
      return false;
}
int main(){
   int n,i,nr,j;
   punct c,d;
   double dx,dy;
   freopen("patrate3.in","r",stdin);
   freopen("patrate3.out","w",stdout);
   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);
   nr=0;
   for(i=1;i<=n-3;i++)
      for(j=i+1;j<=n-2;j++){
         dx=v[j].x-v[i].x;
         dy=v[j].y-v[i].y;
         if(dx>=0&&dy>=0){
            c.x=v[j].x-dy;
            c.y=v[j].y+dx;
            d.x=v[i].x-dy;
            d.y=v[i].y+dx;
            if(findt(d,n)&&findt(c,n))
               nr++;
         }
      }
   printf("%d",nr);
   return 0;
}