Pagini recente » Cod sursa (job #152048) | Monitorul de evaluare | Cod sursa (job #1040056) | Cod sursa (job #2076084) | Cod sursa (job #1035880)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <math.h>
std::ifstream fin("triang.in");
std::ofstream fout("triang.out");
struct punct
{
double x, y;
};
struct triunghi
{
punct a, b, c;
};
int n;
punct vec[1501];
punct mostLeft, mostRight;
inline bool cmp(punct a, punct b)
{
if(a.x < b.x)
{
return true;
}
return false;
}
void citire()
{
fin>>n;
mostLeft.x = 10001;
mostRight.x = -10001;
for(int i = 0; i < n; i++)
{
fin>>vec[i].x>>vec[i].y;
if(vec[i].x < mostLeft.x)
{
mostLeft.x = vec[i].x;
}
else
if(vec[i].x > mostRight.x)
{
mostRight.x = vec[i].x;
}
}
}
void getTheMoFoPoint(punct a, punct b, punct puncte[])
{
puncte[0].x = (double) (((b.x + a.x) - sqrt(3) * (b.y - a.y)) / 2) * (-1);
puncte[0].y = (double) (((b.y + a.y) + sqrt(3) * (b.x - a.x)) / 2);
puncte[1].x = (double) (((b.x + a.x) + sqrt(3) * (b.y - a.y)) / 2);
puncte[1].y = (double) (((b.y + a.y) - sqrt(3) * (b.x - a.x)) / 2);
// std::cout<<(1 / 2) * ((b.x + a.x) - sqrt(3) * (b.y - a.y))<<'\n';
// std::cout<<puncte[0].x<<' '<<puncte[0].y<<"; "<<puncte[1].x<<' '<<puncte[1].y<<'\n';
}
bool binSearch(punct a)
{
int left = 0, right = n - 1;
while(left < right)
{
int m = left / 2 + right / 2;
if(vec[m].x < a.x - 0.001)
{
// std::cout<<vec[m].x<<' '<<a.x - 0.001<<'\n';
// std::cout<<"here1"<<'\n';
left = m + 1;
}
else
if(vec[m].x > a.x + 0.001)
{
// std::cout<<"here2"<<'\n';
right = m - 1;
}
else
{
if(vec[m].y <= a.y + 0.001 && vec[m].y >= a.y - 0.001)
{
return true;
}
return false;
}
}
return false;
}
void rezolvare()
{
std::sort(vec, vec+n, cmp);
int nr = 0;
for(int i = 0; i < n - 1; i++)
{
for(int j = i + 1; j < n; j++)
{
punct pun[2];
getTheMoFoPoint(vec[i], vec[j], pun);
// std::cout<<i<<' '<<j<<": "<<pun[0].x<<' '<<pun[0].y<<"; "<<pun[1].x<<' '<<pun[1].y<<'\n';
// std::cout<<binSearch(pun[0])<<' '<<binSearch(pun[1])<<'\n';
if(binSearch(pun[0]))
{
nr++;
}
if(binSearch(pun[1]))
{
nr++;
}
}
}
fout<<nr<<'\n';
// for(int i = 0; i < n; i++)
// {
// std::cout<<vec[i].x<<' '<<vec[i].y<<'\n';
// }
}
int main()
{
citire();
rezolvare();
return 0;
}