Pagini recente » Cod sursa (job #564857) | Cod sursa (job #146335) | Cod sursa (job #184863) | Cod sursa (job #1655383) | Cod sursa (job #949778)
Cod sursa(job #949778)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX_N = 1510;
const double sin60 = sqrt(3.0) / 2;
const double cos60 = 1.0 / 2;
const double EPSILON = 1e-3;
struct punct {double x, y;} p[MAX_N];
int N;
int sol;
void read(), solve(), print();
int main() {
read();
solve();
print();
return 0;
}
bool cmp(punct a, punct b) {
return ((b.x - a.x > EPSILON) || ((fabs(b.x - a.x) < EPSILON) && (b.y - a.y > EPSILON)));
}
void read() {
ifstream fin("triang.in");
fin >> N;
for (int i = 1; i <= N; ++i) {
fin >> p[i].x >> p[i].y;
}
}
bool binary_search(int lo, int hi, punct pct) {
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (fabs(p[mid].x - pct.x) < EPSILON && fabs(p[mid].y - pct.y) < EPSILON) {
return true;
} else if (cmp(p[mid], pct)) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return false;
}
void solve() {
sort(p + 1, p + N + 1, cmp);
punct pct;
for (int i = 1; i <= N; ++i) {
for (int j = i + 1; j < N; ++j) {
pct.x = p[i].x + (p[j].x - p[i].x) * cos60 - (p[j].y - p[i].y) * sin60;
pct.y = p[i].y + (p[j].y - p[i].y) * cos60 + (p[j].x - p[i].x) * sin60;
if (binary_search(j + 1, N, pct)) ++sol;
pct.x = p[i].x + (p[j].x - p[i].x) * cos60 + (p[j].y - p[i].y) * sin60;
pct.y = p[i].y + (p[j].y - p[i].y) * cos60 - (p[j].x - p[i].x) * sin60;
if (binary_search(j + 1, N, pct)) ++sol;
}
}
}
void print() {
ofstream fout("triang.out");
fout << sol;
}