Pagini recente » Cod sursa (job #1838927) | Cod sursa (job #2709560) | Cod sursa (job #1102110) | Cod sursa (job #357313) | Cod sursa (job #592017)
Cod sursa(job #592017)
#include <cmath>
#include <fstream>
#include <algorithm>
using namespace std;
#define x first
#define y second
const double CONST = sqrt(3);
const double eps = 0.0001;
int N, triang;
pair<double, double> P[1502];
int compare(const pair<double, double>& p1, const pair<double, double>& p2)
{
if (p1.x - p2.x < -eps) return 0;
if (p2.x - p1.x < -eps) return 2;
if (p1.y - p2.y < -eps) return 0;
if (p2.y - p1.y < -eps) return 2;
return 1;
}
bool sortcomp(const pair<double, double>& p1, const pair<double, double>& p2)
{
if (fabs(p1.x - p2.x) < eps)
return (p1.y - p2.y < -eps);
return (p1.x - p2.x < -eps);
}
int main()
{
ifstream fin("triang.in");
ofstream fout("triang.out");
fin >> N;
for (int i = 1; i <= N; ++i)
fin >> P[i].x >> P[i].y;
sort(P + 1, P + N + 1, sortcomp);
int logN, step, now;
for (logN = 1; (logN << 1) <= N; logN <<= 1);
for (int i = 1; i <= N; ++i)
for (int j = i + 1; j <= N; ++j)
{
if (compare(P[i], P[j]) == 1) continue;
pair<double, double> mid;
mid.x = (P[i].x + P[j].x) / 2;
mid.y = (P[i].y + P[j].y) / 2;
pair<double, double> dist;
dist.x = P[i].x - mid.x;
dist.y = P[i].y - mid.y;
dist.x *= CONST, dist.y *= CONST;
pair<double, double> point1, point2;
point1.x = mid.x + dist.y;
point1.y = mid.y + dist.x;
point2.x = mid.x - dist.y;
point2.y = mid.y - dist.x;
// point1
step = logN;
for (now = 0; step; step >>= 1)
if (now + step <= N && compare(P[now + step], point1) != 2)
now += step;
triang += (compare(P[now], point1) == 1);
// point2
step = logN;
for (now = 0; step; step >>= 1)
if (now + step <= N && compare(P[now + step], point2) != 2)
now += step;
triang += (compare(P[now], point2) == 1);
}
fout << triang;
fin.close();
fout.close();
}