Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- struct Dot {
- Dot(long double x, long double y) : x(x), y(y) {}
- Dot operator-(Dot other) const {
- return {x - other.x, y - other.y};
- }
- long double x;
- long double y;
- };
- struct Line {
- Line(long double x1, long double y1, long double x2, long double y2) : a(y1 - y2), b(x2 - x1),
- c(x1 * (y2 - y1) - y1 * (x2 - x1)) {}
- long double c;
- long double a;
- long double b;
- };
- double scal_prod(Dot first, Dot second) {
- return first.x * second.x + first.y * second.y;
- }
- double skew_prod(Dot first, Dot second) {
- return first.x * second.y - second.x * first.y;
- }
- bool IsDotInsideSegment(Dot target, Dot a, Dot b) {
- Dot p1p2 = b - a;
- Dot p1m = target - a;
- Dot mp1 = a - target;
- Dot mp2 = b - target;
- if (skew_prod(p1p2, p1m) == 0 && scal_prod(mp1, mp2) <= 0) {
- return true;
- } else {
- return false;
- }
- }
- bool AreDotsOnDiffSides(Dot p1, Dot p2, Dot m1, Dot m2) {
- Dot p1p2 = p2 - p1;
- Dot p1m2 = m2 - p1;
- Dot p1m1 = m1 - p1;
- if (skew_prod(p1p2, p1m2) * skew_prod(p1p2, p1m1) < 0) {
- return true;
- } else {
- return false;
- }
- }
- std::vector<Dot> Graham(std::vector<Dot>& dots) {
- Dot start = dots.front();
- for (Dot d : dots) { // ищем старт
- if (d.x < start.x || (d.x == start.x && d.y < start.y)) {
- start = d;
- }
- }
- for (Dot& d : dots) { // делаем start началом координат
- d.x -= start.x;
- d.y -= start.y;
- }
- std::sort(dots.begin(), dots.end(), [&](Dot a, Dot b) { // сортим точки по полярному углу
- return skew_prod(a, b) > 0 || skew_prod(a, b) == 0 && a.x * a.x + a.y * a.y < b.x * b.x + b.y * b.y;
- });
- std::vector<Dot> stack;
- for (Dot d : dots) {
- while (stack.size() >= 2) {
- Dot last = d - stack.back();
- Dot pre_last = stack[stack.size() - 2] - stack.back();
- if (skew_prod(last, pre_last) <= 0) {
- stack.pop_back();
- } else {
- break;
- }
- }
- stack.push_back(d);
- }
- return stack;
- }
- long double count_square(std::vector<Dot>& dots) {
- long double square = 0;
- for (int i = 0; i < dots.size() - 1; ++i) {
- square += skew_prod(dots[i], dots[i+1]);
- }
- square += skew_prod(dots.back(), dots.front());
- square = square / 2;
- return std::abs(square);
- }
- long double count_perimeter(std::vector<Dot>& dots) {
- long double perimeter = 0;
- for (int i = 0; i < dots.size() - 1; ++i) {
- perimeter += sqrt(std::pow(dots[i+1].x - dots[i].x, 2) + std::pow(dots[i+1].y - dots[i].y, 2));
- }
- perimeter += sqrt(std::pow(dots.back().x - dots.front().x, 2) + std::pow(dots.back().y - dots.front().y, 2));
- return perimeter;
- }
- int main() {
- int n;
- std::cin >> n;
- std::vector<Dot> dots;
- for (int i = 0; i < n; ++i) {
- long double x, y;
- std::cin >> x >> y;
- dots.emplace_back(Dot(x, y));
- }
- std::vector<Dot> hull = Graham(dots);
- std::cout << count_perimeter(hull) << std::endl << count_square(hull);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement