Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <algorithm>
- #include <iostream>
- #include <cmath>
- using namespace std;
- class Point {
- public:
- long long x, y;
- Point(long long x, long long y) : x(x), y(y) {}
- Point() = default;
- friend istream& operator>>(istream& in, Point& p) {
- cin >> p.x >> p.y;
- return in;
- }
- };
- class Vector {
- long long x, y;
- public:
- Vector() = default;
- Vector(long long x, long long y) : x(x), y(y) {}
- Vector(Point a, Point b) : x(b.x - a.x), y(b.y - a.y) {}
- Vector operator * (long long b) {
- return {x * b, y * b};
- }
- Vector operator / (long long b) {
- return {x / b, y / b};
- }
- Vector operator + (const Vector& o) {
- return {x + o.x, y + o.y};
- }
- friend long long operator^(const Vector& a, const Vector& b) {
- return a.x*b.y - a.y*b.x;
- }
- };
- class Polygon {
- public:
- vector<Point> p;
- long long pnum;
- friend istream& operator>>(istream& in, Polygon& p) {
- cin >> p.pnum;
- for (int i = 0; i < p.pnum; ++i) {
- Point x;
- cin >> x;
- p.p.push_back(x);
- }
- return in;
- }
- void Sq() {
- long long sq = 0;
- Point strt(0, 0);
- for (int i = 0; i < pnum - 1; i++) {
- Vector p1(strt, p[i]);
- Vector p2(strt, p[i + 1]);
- sq += (p1 ^ p2);
- }
- Vector p1(strt, p[pnum - 1]);
- Vector p2(strt, p[0]);
- sq += (p1 ^ p2);
- if (sq % 2 == 1 || sq % 2 == -1) {
- cout << abs(sq / 2) << ".5";
- } else {
- cout << abs(sq / 2);
- }
- }
- };
- bool q1(Point a, Point b) {
- return a.x < b.x || a.x == b.x && a.y < b.y;
- }
- bool q2(Point a, Point b, Point c) {
- return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;
- }
- bool q3(Point a, Point b, Point c) {
- return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;
- }
- void obolo(vector<Point> &a) {
- if (a.size() == 1) return;
- sort(a.begin(), a.end(), &q1);
- Point p1 = a[0], p2 = a.back();
- vector<Point> up, down;
- up.push_back (p1);
- down.push_back (p1);
- for (size_t i=1; i<a.size(); ++i) {
- if (i==a.size()-1 || q2(p1, a[i], p2)) {
- while (up.size()>=2 && !q2(up[up.size() - 2], up[up.size() - 1], a[i]))
- up.pop_back();
- up.push_back (a[i]);
- }
- if (i==a.size()-1 || q3(p1, a[i], p2)) {
- while (down.size()>=2 && !q3(down[down.size() - 2], down[down.size() - 1], a[i]))
- down.pop_back();
- down.push_back (a[i]);
- }
- }
- a.clear();
- for (size_t i=0; i<up.size(); ++i)
- a.push_back (up[i]);
- for (size_t i=down.size()-2; i>0; --i)
- a.push_back (down[i]);
- }
- int main() {
- cout.precision(15);
- Polygon p{};
- cin >> p;
- obolo(p.p);
- p.pnum = p.p.size();
- cout << p.pnum << endl;
- for (Point i: p.p) {
- Point x = i;
- cout << x.x << ' ' << x.y << endl;
- }
- p.Sq();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement