Pagini recente » Cod sursa (job #1120579) | Diferente pentru utilizator/raresegay intre reviziile 11 si 12 | Cod sursa (job #23632) | Cod sursa (job #1513717) | Cod sursa (job #2339617)
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'
using namespace std;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int NMAX = 1505;
const ld EPS = 1e-6;
int sign (const ld x) {
if (fabs (x) <= EPS) return 0;
return (x < 0) ? -1 : 1;
}
struct Point {
ld x, y;
Point (ld _x = 0, ld _y = 0) : x (_x), y (_y) {}
Point middle (const Point &other) {
return {0.5 * (x + other.x), 0.5 * (y + other.y)};
}
ld sqrDist (const Point &other) {
return ((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y));
}
bool operator < (const Point &other) const {
if (sign (x - other.x) == 0) return y < other.y;
return x < other.x;
}
bool operator == (const Point &other) const {
return sign (x - other.x) == 0 && sign (y - other.y) == 0;
}
bool operator != (const Point &other) const {
return !(*this == other);
}
};
struct Line {
ld a, b, c;
Line (ld _a = 0, ld _b = 0, ld _c = 0) : a (_a), b (_b), c (_c) {}
Line (const Point &_a, const Point &_b) : a (_a.y - _b.y), b (_b.x - _a.x), c (_a.x * _b.y - _b.x * _a.y) {}
Line perpendicular (const Point &p) {
return {b, -a, a * p.y - b * p.x};
}
ld yAtX (const ld x) {
return (-a / b) * x - c / b;
}
pair <Point, Point> pointAtDistance (const Point &p, const ld sqr_dist) {
pair <Point, Point> ret;
if (a == 0) {
ret.fi.y = ret.se.y = p.y;
ret.fi.x = p.x - sqrt (sqr_dist);
ret.se.x = p.x + sqrt (sqr_dist);
return ret;
}
if (b == 0) {
ret.fi.x = ret.se.x = p.x;
ret.fi.y = p.y - sqrt (sqr_dist);
ret.se.y = p.y + sqrt (sqr_dist);
return ret;
}
ld delta = b * sqrt ((a * a + b * b) * sqr_dist * sqr_dist * sqr_dist * sqr_dist - c * c);
ld x = (-a * c + delta) / (a * a + b * b);
ret.fi.x = p.x + x;
ret.fi.y = yAtX (ret.fi.x);
x = (-a * c - delta) / (a * a + b * b);
ret.se.x = p.x + x;
ret.se.y = yAtX (ret.se.x);
assert (ret.fi != ret.se);
return ret;
}
};
int n;
Point points[NMAX];
bool check (const Point &p, const Point &comp) {
if (sign (p.x - comp.x) != 0) return p.x < comp.x;
return sign (p.y - comp.y) <= 0;
}
bool findPoint (int lo, const Point &p) {
if (lo > n) return false;
int hi = n;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (check (points[mid], p)) {
lo = mid;
} else {
hi = mid - 1;
}
}
return check (points[lo], p);
}
const ld sin60 = sqrt (3) / 2;
const ld cos60 = 0.5;
const ld sin_min60 = -sin60;
const ld cos_min60 = cos60;
pair <Point, Point> getThird (Point a, Point b) {
ld x = b.x - a.x;
ld y = b.y - a.y;
pair <Point, Point> ret;
ret.fi.x = a.x + x * cos60 - y * sin60;
ret.fi.y = a.y + y * cos60 + x * sin60;
ret.se.x = a.x + x * cos_min60 - y * sin_min60;
ret.se.y = a.y + y * cos_min60 + x * sin_min60;
return ret;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL_DEFINE
freopen (".in", "r", stdin);
#endif
ifstream f ("triang.in");
ofstream g ("triang.out");
f >> n;
for (int i = 1; i <= n; ++i) {
f >> points[i].x >> points[i].y;
}
sort (points + 1, points + n + 1);
int answer = 0;
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
pair <Point, Point> c = getThird (points[i], points[j]);
if (findPoint (j + 1, c.fi)) ++answer;
if (findPoint (j + 1, c.se)) ++answer;
}
}
g << answer << '\n';
f.close();
g.close();
#ifdef LOCAL_DEFINE
fprintf (stderr, "Time elapsed: %lf s.\n", 1.0 * clock() / CLOCKS_PER_SEC);
#endif
return 0;
}