Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Исходный код
- #include<bits/stdc++.h>
- #define INF 1000010000
- #define nl '\n'
- #define pb push_back
- #define ppb pop_back
- #define mp make_pair
- #define fi first
- #define se second
- #define pii pair<int,int>
- #define pdd pair<double,double>
- #define all(c) (c).begin(), (c).end()
- #define SORT(c) sort(all(c))
- #define rep(i,n) for( int i = 0; i < n; ++i )
- #define repi(i,n) for( int i = 1 ; i <= n; ++i )
- #define repn(i,n) for( int i = n ; i > 0 ; --i )
- #define repf(j,i,n) for( int j = i ; j < n ; ++j )
- #define die(s) {std::cout << s << nl;}
- #define dier(s) {std::cout << s; return 0;}
- #define vi vector<int>
- typedef long long ll;
- using namespace std;
- struct point
- {
- int x,y;
- inline point(int _x,int _y){
- x=_x;
- y=_y;
- }
- };
- inline bool cmp(point a,point b){
- return a.x < b.x || a.x==b.x && a.y < b.y;
- }
- inline bool cw(point a,point b,point c){
- return ((a.x - b.x) * (c.y - b.y) - (c.x - b.x) * (a.y - b.y)) < 0;
- }
- inline bool ccw(point a,point b,point c){
- return ((a.x - b.x) * (c.y - b.y) - (c.x - b.x) * (a.y - b.y)) > 0;
- }
- inline double dist(point a,point b){
- return sqrt(double((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)));
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- // cout.precision(1);
- vector<point> v;
- int n;
- cin >> n;
- int x , y;
- rep(i , n){
- cin >> x >> y;
- v.pb(point(x , y));
- }
- sort(all(v) , cmp);
- vector<point> up , down;
- point p1 = v[0] , p2=v.back();
- double ans = 0;
- up.pb(p1);
- down.pb(p1);
- repf(i , 1 , v.size() ){
- if(i == v.size() - 1 || cw(p1 , v[i] , p2)){
- while(up.size() > 1 && !cw(up[up.size() - 2] , up[up.size() - 1] , v[i])) up.ppb();
- up.pb(v[i]);
- }
- if(i == v.size() - 1 || ccw(p1 , v[i] , p2)){
- while(down.size() > 1 && !ccw(down[down.size() - 2] , down[down.size() - 1] , v[i])) down.ppb();
- down.pb(v[i]);
- }
- }
- v.clear();
- rep(i , up.size()) v.pb(up[i]);
- repn(i , down.size() - 2) v.pb(down[i]);
- v.pb(v[0]);
- rep(i , v.size() - 1) ans += dist(v[i] , v[i+1]);
- printf("%.1lf\n", ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement