Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef struct point {
- long long x, y;
- point() {}
- point(long long x, long long y) : x(x), y(y) {}
- };
- point operator+(point p1, point p2) {
- return point(p1.x + p2.x, p1.y + p2.y);
- }
- point operator-(point p1) {
- return point(-p1.x, -p1.y);
- }
- point operator-(point p1, point p2) {
- return p1 + (-p2);
- }
- long long dot(point p1, point p2) {
- return p1.x * p2.x + p1.y * p2.y;
- }
- long long cross(point p1, point p2) {
- return p1.x * p2.y - p1.y * p2.x;
- }
- bool cmp(point &a, point &b) {
- if (a.x != b.x)
- return a.x < b.x;
- return a.y < b.y;
- }
- void build_convex_hull(vector<point> &pst, vector<point> &ch) {
- vector<point> lower_hull, upper_hull;
- lower_hull.push_back(pst[0]);
- upper_hull.push_back(pst[0]);
- long double k = (long double)(pst.back().y - pst[0].y) / (pst.back().x - pst[0].x), m = pst[0].y - pst[0].x * k;
- for (int i = 1; i < pst.size(); i++) {
- if (pst[i].y > k * pst[i].x + m || i == pst.size() - 1) {
- while (upper_hull.size() > 1 && cross(pst[i] - upper_hull[upper_hull.size() - 2], upper_hull.back() - upper_hull[upper_hull.size() - 2]) <= 0)
- upper_hull.pop_back();
- upper_hull.push_back(pst[i]);
- }
- if (pst[i].y < k * pst[i].x + m || i == pst.size() - 1) {
- while (lower_hull.size() > 1 && cross(pst[i] - lower_hull[lower_hull.size() - 2], lower_hull.back() - lower_hull[lower_hull.size() - 2]) >= 0)
- lower_hull.pop_back();
- lower_hull.push_back(pst[i]);
- }
- }
- for (int i = 0; i < upper_hull.size(); i++)
- ch.push_back(upper_hull[i]);
- for (int i = lower_hull.size() - 2; i >= 1 ; i--)
- ch.push_back(lower_hull[i]);
- }
- long double get_polygon_area(vector<point> &polygon) {
- long long ar = 0;
- for (int i = 0; i < polygon.size() - 1; i++)
- ar += cross(polygon[i], polygon[i + 1]);
- ar += cross(polygon.back(), polygon[0]);
- return abs(ar) / 2.;
- }
- int main() {
- //freopen("hull.in", "r", stdin);
- //freopen("hull.out", "w", stdout);
- int n;
- long long s;
- cin >> n;//>> s;
- vector<point> pts(n);
- long long j = 0;
- for (int i = 0; i < n; i++) {
- //pts[i] = point(i, i * i);
- cin >> pts[i].x >> pts[i].y;
- }
- vector<point> nvc;
- sort(pts.begin(), pts.end(), cmp);
- nvc.push_back(pts[0]);
- for (int i = 1; i < pts.size(); i++)
- if (pts[i].x != pts[i - 1].x || pts[i].y != pts[i - 1].y)
- nvc.push_back(pts[i]);
- pts = nvc;
- if (nvc.size() == 1) {
- cout << "1\n" << nvc[0].x << ' ' << nvc[0].y << "\n0";
- return 0;
- }
- if (pts[0].x == pts.back().x) {
- cout << "2\n" << pts[0].x << ' ' << pts[0].y << '\n';
- cout << pts.back().x << ' ' << pts.back().y << "\n0";
- return 0;
- }
- vector<point> convex_hull;
- build_convex_hull(pts, convex_hull);
- //cout << convex_hull.size() << '\n';
- //for (int i = 0; i < convex_hull.size(); i++)
- // cout << convex_hull[i].x << ' ' << convex_hull[i].y << '\n';
- long double gg = 0;
- for (int i = 1; i < convex_hull.size(); i++)
- gg += sqrt((convex_hull[i].x - convex_hull[i - 1].x) * (convex_hull[i].x - convex_hull[i - 1].x) + (convex_hull[i].y - convex_hull[i - 1].y) * (convex_hull[i].y - convex_hull[i - 1].y));
- gg += sqrt((convex_hull[0].x - convex_hull.back().x) * (convex_hull[0].x - convex_hull.back().x) + (convex_hull[0].y - convex_hull.back().y) * (convex_hull[0].y - convex_hull.back().y));
- cout << setprecision(20) << gg << '\n' << get_polygon_area(convex_hull) << '\n';
- return 0;
- }
- /*
- 4499550010000
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement