Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <cmath>
- #include <map>
- #include <iomanip>
- #define pb push_back
- #define fst first
- #define snd second
- #define forn(i,n) forr(i,0,n)
- #define forr(i,x,n) for(int i=(x); i<int(n); i++)
- using namespace std;
- typedef unsigned long long ll;
- const ll MAXN = 200005;
- const ll INF = 1e18;
- const ll MOD = 1e9 + 7;
- struct pt {
- double x, y;
- int id;
- pt(double x=0, double y=0, int id=0):x(x),y(y),id(id){}
- pt operator-(pt a){return pt(x-a.x, y-a.y);}
- double norm(){return sqrt(x*x+y*y);}
- };
- double dist(pt a, pt b){return (b-a).norm();}
- bool cmp (pt a, pt b) {
- return a.x <b.x || a.x == b.x && a.y <b.y;
- }
- bool cw (pt a, pt b, pt c) {
- return a.x * (b.y-c.y) + b.x * (c.y-a.y) + c.x * (a.y-b.y) <0;
- }
- bool ccw (pt a, pt b, pt c) {
- return a.x * (b.y-c.y) + b.x * (c.y-a.y) + c.x * (a.y-b.y)> 0;
- }
- void convex_hull (vector <pt> & a) {
- if (a.size () == 1) return;
- sort (a.begin (), a.end (), & cmp);
- pt p1 = a [0], p2 = a.back ();
- vector <pt> up, down;
- up.push_back (p1);
- down.push_back (p1);
- for (size_t i = 1; i <a.size (); ++ i) {
- if (i == a.size () - 1 || cw (p1, a [i], p2)) {
- while (up.size () >= 2 &&! cw (up [up.size () - 2], up [up.size () - 1], a [i]))
- up.pop_back ();
- up.push_back (a [i]);
- }
- if (i == a.size () - 1 || ccw (p1, a [i], p2)) {
- while (down.size () >= 2 &&! ccw (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 N;
- vector<pt> V;
- int main(){
- ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
- cin >> N;
- forn(i,N){
- double a, b;
- cin >> a >> b;
- V.push_back({a,b,i});
- }
- convex_hull(V);
- double perim = 0;
- forn(i, V.size()) perim += dist(V[i], V[(i+1)%V.size()]);
- cout << fixed << setprecision(0) << perim << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement