Cod sursa(job #1931192)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 19 martie 2017 12:50:31
Problema Patrate 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
struct punct {
  double x, y;
};
punct v[1001];
bool cmp(punct a,punct b){
   if(fabs(a.y-b.y)<=1e-9&&fabs(a.x-b.x)<=1e-9)
      return true;
   else if(fabs(a.y-b.y)<=1e-9)
      return a.x<b.x;
   else
      return a.y<b.y;
}
bool find(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(fabs(a.x-v[poz].x)<=1e-9&&fabs(a.y-v[poz].y)<=1e-9)
      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;i++)
      for(j=i+1;j<=n;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(find(d,n)&&find(c,n))
               nr++;
         }
      }
   printf("%d",nr);
  return 0;
}