Pagini recente » Cod sursa (job #123536) | Cod sursa (job #1033330) | Cod sursa (job #1172713) | Cod sursa (job #1464238) | Cod sursa (job #1551593)
#include <cmath>
#include <fstream>
#include <vector>
#include <algorithm>
struct Point {
double x, y;
};
static auto const epsilon = 0.001;
static auto are_equal_epsilon(Point pa, Point pb) -> bool {
return std::abs(pa.x - pb.x) < epsilon && std::abs(pa.y - pb.y) < epsilon;
}
// given two points p1 and p2 with p2.x > p1.x
// returns the 3rd point to form an equilateral triangle.
// From the two such possible choices returns the rightmost;
static auto get_3rd_point(Point const &p1, Point const &p2) -> Point {
// rotate 60 or -60 degress
auto const sin_60 = (p2.y < p1.y ? 1 : -1) *
0.8660254037844386467637231707529361834714026269051903;
auto const cos_60 = 0.5;
return {p1.x + (p2.x - p1.x) * cos_60 - (p2.y - p1.y) * sin_60,
p1.y + (p2.x - p1.x) * sin_60 + (p2.y - p1.y) * cos_60};
}
using const_points_iterator = std::vector<Point>::const_iterator;
auto contains(const_points_iterator first, const_points_iterator last,
const Point &p) -> bool {
while (first < last) {
auto const mid = first + (last - first) / 2;
if (are_equal_epsilon(*mid, p))
return true;
if (p.x < mid->x)
last = mid;
else
first = mid + 1;
}
return false;
}
auto main() -> int {
std::ifstream fin{"triang.in"};
auto points = std::vector<Point>();
auto n = int{};
fin >> n;
auto const size = n;
points.reserve(size);
for (auto i = 0; i < size; ++i) {
Point p;
fin >> p.x >> p.y;
points.emplace_back(p);
}
fin.close();
auto num = 0;
std::sort(std::begin(points), std::end(points),
[](Point const &p_a, Point const &p_b) { return p_a.x < p_b.x; });
for (auto i = 0; i < size; ++i) {
for (auto j = i + 1; j < size; ++j) {
auto p3 = get_3rd_point(points[i], points[j]);
if (p3.x < points[j].x)
continue;
if (contains(points.cbegin() + j + 1, points.cend(), p3)) {
++num;
}
}
}
std::ofstream fout("triang.out");
fout << num;
return 0;
}