Pagini recente » Cod sursa (job #2259897) | Cod sursa (job #1078706) | Cod sursa (job #3268671) | Cod sursa (job #3175506) | Cod sursa (job #3223248)
#include <fstream>
#include <set>
#include <cassert>
#include <stack>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;
ifstream cin("triang.in");
ofstream cout("triang.out");
const int NMAX = 1500;
const double EPS = 1e-3;
const double SQRT3 = 1.7320508075688772935274463415059;
struct Point
{
double x, y;
void Read()
{
cin >> x >> y;
}
};
struct Line
{
double a, b, c;
};
int n, answer;
Point points[NMAX + 1];
bool cmpP(const Point& p1, const Point& p2)
{
/// p1.x < p2.x
/// p1.x < p2.x - EPS
if (p1.x < p2.x - EPS)
return true;
if (abs(p1.x - p2.x) < EPS && p1.y < p2.y - EPS)
return true;
return false;
}
bool cmpP2(const Point& p1, const Point& p2)
{
if (p1.x < p2.x - EPS)
return true;
if (abs(p1.x - p2.x) < EPS && p1.y < p2.y - EPS)
return true;
if (abs(p1.x - p2.x) < EPS && abs(p1.y - p2.y) < EPS)
return true;
return false;
}
bool BS(Point p)
{
int left = 1, right = n, pos = 0;
while (left <= right)
{
int mid = (left + right) / 2;
if (cmpP2(points[mid], p))
pos = mid, left = mid + 1;
else
right = mid - 1;
}
if (abs(points[pos].x - p.x) < EPS && abs(points[pos].y - p.y) < EPS)
return true;
return false;
}
double Square(double x)
{
return x * x;
}
double Distance(Point p1, Point p2)
{
return (Square(p1.x - p2.x) + Square(p1.y - p2.y));
}
pair<double, double> SolveEQ2(double a, double b, double c)
{
double delta = Square(b) - 4 * a * c;
pair<double, double> answer;
answer.first = (-b + sqrt(delta)) / (2 * a);
answer.second = (-b - sqrt(delta)) / (2 * a);
return answer;
}
void Solve(Point p1, Point p2)
{
Point mid = { (p1.x + p2.x) / 2, (p1.y + p2.y) / 2 };
Line mediator_line;
mediator_line.a = p2.x - p1.x;
mediator_line.b = p2.y - p1.y;
mediator_line.c = -mid.y * (p2.y - p1.y) - mid.x * (p2.x - p1.x);
double A = -mediator_line.b / mediator_line.a;
double B = -mediator_line.c / mediator_line.a;
double V = 3 * Distance(p1, p2) / 4;
double a = Square(A) + 1;
double b = 2 * A * B - 2 * mid.x * A - 2 * mid.y;
double c = Square(B) - 2 * mid.x * B + Square(mid.x) + Square(mid.y) - V;
pair<double, double> y = SolveEQ2(a, b, c);
pair<double, double> x;
x.first = y.first * A + B;
x.second = y.second * A + B;
if (BS({ x.first, y.first }))
answer++;
if (BS({ x.second, y.second }))
answer++;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
points[i].Read();
sort(points + 1, points + n + 1, cmpP);
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
Solve(points[i], points[j]);
cout << answer / 3;
return 0;
}