Pagini recente » Cod sursa (job #98540) | Cod sursa (job #279297) | Cod sursa (job #2639447) | Cod sursa (job #1549822) | Cod sursa (job #2310351)
#include <fstream>
#include <algorithm>
#define nmax 1001
using namespace std;
ifstream fin("patrate3.in");
ofstream fout("patrate3.out");
struct punct
{ double x,y;
};
const double VAL=0.0001;
///date de intrare
int n;
punct v[nmax];
///date de iesire
int nr_patrate;
double mod(double x,double y)///functia modul
{ if(x > y) return (x-y);
else return (y-x);
}
int cmp(punct A,punct B) ///functie 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_Punct(punct A)
{
int gasit=0;
int st=1,dr=n;
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 n;
fin>>n;
int i,j;
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(mij.x , A.x);
double dy = mod(mij.y , A.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_Punct(C)==1 && Cautare_Binara_Punct(D)==1)
nr_patrate++;
}
fout<<nr_patrate/2;
return 0;
}