Mai intai trebuie sa te autentifici.
Cod sursa(job #2002340)
Utilizator | Data | 19 iulie 2017 14:22:13 | |
---|---|---|---|
Problema | Patrate 3 | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Teme Pregatire ACM Unibuc 2013 | Marime | 1.86 kb |
#include <fstream>
#include <algorithm>
#define VAL 1005
#define F first
#define S second
using namespace std;
ifstream fin("patrate3.in");
ofstream fout("patrate3.out");
int N, ans, i, j;
double H, L;
pair <double, double> pct, P1, P2;
pair <double, double> P[VAL];
bool Binary_Search(pair <double, double> pct)
{
int be=1, en=N;
int mid;
while (be<=en)
{
mid=(be+en) / 2;
if (P[mid].F==pct.F && P[mid].S==pct.S)
return true;
else
{
if (P[mid].F<pct.F || (P[mid].F==pct.F && P[mid].S<pct.S))
be=mid+1;
if (P[mid].F>pct.F || (P[mid].F==pct.F && P[mid].S>pct.S))
en=mid-1;
}
}
return false;
}
int main()
{
fin >> N;
for (i=1; i<=N; i++)
fin >> P[i].F >> P[i].S;
sort(P+1, P+N+1);
for (i=1; i<N; i++)
{
for (j=i+1; j<=N; j++)
{
pct.F=(P[i].F+P[j].F) / 2;
pct.S=(P[i].S+P[j].S) / 2;
H=pct.F-P[i].F;
L=pct.S-P[i].S;
if (P[i].S<=P[j].S)
{
P1.F=pct.F-L;
P1.S=pct.S+H;
P2.F=pct.F+L;
P2.S=pct.S-H;
if (Binary_Search(P1)==true && Binary_Search(P2)==true)
ans++;
}
else
{
P1.F=pct.F-L;
P1.S=pct.S+H;
P2.F=pct.F+L;
P2.S=pct.S-H;
if (Binary_Search(P1)==true && Binary_Search(P2)==true)
ans++;
}
/*fout << P[i].F << " " << P[i].S << '\n';
fout << P[j].F << " " << P[j].S << '\n';
fout << P1.F << " " << P1.S << '\n';
fout << P2.F << " " << P2.S << '\n';
fout << '\n';*/
}
}
fout << ans / 2 << '\n';
fin.close();
fout.close();
return 0;
}