Pagini recente » Cod sursa (job #3142777) | Cod sursa (job #2368309) | Cod sursa (job #1768999) | Cod sursa (job #1374586) | Cod sursa (job #2310434)
#include <algorithm>
#include <fstream>
#define nmax 1001
using namespace std;
ifstream fin("patrate3.in");
ofstream fout("patrate3.out");
const double VAL=0.0001;
struct punct
{ double x,y;
};
///date de intrare
punct v[nmax];
int n;
///date de iesiere
int nr_patrate;
double mod(double x,double y) ///functia modul
{
if(x>y) return x-y;
else return y-x;
}
bool cmp(punct A,punct B) ///functia de comparare
{
if(A.x==B.x)
{
if(A.y<=B.y) return 1;
else return 0;
}
else
{
if(A.x<=B.x) return 1;
else return 0;
}
}
int Cautare_Binara_Puncte(punct A) ///cautarea unui punct in vectorul de puncte
{
int st=1;
int dr=n;
int gasit=0;
while(st<=dr && gasit==0)
{
int mij=(st+dr)/2;
if(mod(v[mij].x,A.x)<VAL && mod(v[mij].y,A.y)<VAL) gasit=1;
else
{
if(mod(v[mij].x,A.x)<VAL)
{
if(A.y<v[mij].y) dr=mij-1;
else st=mij+1;
}
else
{ if(A.x<v[mij].x) dr=mij-1;
else st=mij+1;
}
}
}
return gasit;
}
int main()
{
int i,j;
fin>>n;
for(i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
///sortam crescator vectorul de puncte(dupa abscise, iar pt abscise egale dupa ordonate)
sort(v+1,v+n+1,cmp);
///cautam nr de patrate
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
{
///luam 2 puncte din vectorul de puncte si presupunem ca formeaza o diagonala
punct A,B;
A=v[i];
B=v[j];
///aflam celelalte 2 puncte ale patratului
punct C,D;
punct mij; ///mijlocul patratului
mij.x=(A.x+B.x)/2;
mij.y=(A.y+B.y)/2;
double dx=mod(A.x,mij.x);
double dy=mod(A.y,mij.y);
if(A.y<B.y)
{
C.x=mij.x+dy;
C.y=mij.y-dx;
D.x=mij.x-dy;
D.y=mij.y+dx;
}
else
{
C.x=mij.x-dy;
C.y=mij.y-dx;
D.x=mij.x+dy;
D.y=mij.y+dx;
}
///cautam binar cele 2 puncte aflate, iar daca sunt gasite inseamna ca formeaza un patrat cu cele 2 puncte alese initial
if(Cautare_Binara_Puncte(C)==1 && Cautare_Binara_Puncte(D)==1)
nr_patrate++;
}
fout<<nr_patrate/2;
return 0;
}