Pagini recente » Urmasii lui Moisil 2017 | Cod sursa (job #2261791) | Cod sursa (job #2296650) | Cod sursa (job #1284247) | Cod sursa (job #772646)
Cod sursa(job #772646)
#include <cmath>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
#define x first
#define y second
const double EPS = 1e-3;
const double pi = 3.14159265;
const double c60 = cos(pi / 3);
const double s60 = sin(pi / 3);
int n, sol;
double X, Y;
vector <pair <double, double> > a;
int EQUAL(double a, double b)
{
if (fabs(a - b) < EPS)
return 1;
return 0;
}
int LESS(double a, double b)
{
if (a + EPS < b)
return 1;
return 0;
}
int cmp(pair <double, double> a, pair <double, double> b)
{
if(EQUAL(a.x, b.x))
return LESS(a.y, b.y);
return LESS(a.x, b.x);
}
int exista(int left, int right, double X, double Y)
{
while (left <= right) {
int m = left + (right - left) / 2;
if (EQUAL(X, a[m].x) && EQUAL(Y, a[m].y))
return 1;
if (LESS(a[m].x, X) || (EQUAL(a[m].x, X) && LESS(a[m].y, Y)))
left = m + 1;
else
right = m - 1;
}
return 0;
}
int main()
{
ifstream f("triang.in");
ofstream g("triang.out");
f >> n;
for (int i = 1; i <= n; ++i) {
double j, k;
f >> j >> k;
a.push_back(make_pair(j, k));
}
sort(a.begin(), a.end(), cmp);
for (int i = 0; i < n - 2; ++i)
for (int j = i + 1; j < n - 1; ++j) {
X = a[i].x + (a[j].x - a[i].x) * c60 - (a[j].y - a[i].y) * s60;
Y = a[i].y + (a[j].x - a[i].x) * s60 + (a[j].y - a[i].y) * c60;
if (exista(j + 1, n - 1, X, Y))
++sol;
X = a[i].x + (a[j].x - a[i].x) * c60 - (a[j].y - a[i].y) * (-s60);
Y = a[i].y + (a[j].x - a[i].x) * (-s60) + (a[j].y - a[i].y) * c60;
if (exista(j + 1, n - 1, X, Y))
++sol;
}
g << sol;
return 0;
}