program_files/BSHEEP.cpp at master · NishantRaj/program_files · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 22 October 2015 (Thursday) 09:33
===================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define mod 1000000009
class point{
public:
    int x , y , pos;
    point(){};
    point(int a , int b , int c){x = a , y = b , pos = c;}
    double distance(point &a){
        int dx = a.x - x;
        int dy = a.y - y;
        return sqrt(dx*dx + dy*dy);
    }
    bool operator != (point &a){
        if(a.x != x || a.y != y)
            return true;
        return false;
    }
};
bool cmp(const point &a , const point &b){
    return a.y == b.y ? (a.x == b.x ? a.pos < b.pos : a.x < b.x ): a.y < b.y;
}
int orientation( point P , point Q , point R ){
    return  ( Q.x - P.x ) * ( R.y - P.y ) - ( R.x - P.x ) * ( Q.y - P.y );
}
void convex_hull(vector<point> &p , vector<point> &upper , vector<point> &lower){
    sort(p.begin() , p.end() , cmp);
    int k = 1;
    for(int i = 1 ; i < p.size() ; i++)
        if(p[i-1] != p[i])
            p[k++] = p[i];
    p.resize(k);
    int sz = 2*k;
    upper.resize(sz);
    lower.resize(sz);
    int j = 0 ;
    k = 0;
    for(int i = 0 ; i < p.size() ; i++){
        while(j >= 2 && orientation(lower[j-2] , lower[j-1] , p[i]) <= 0)
            j--;
        while(k >=2 && orientation(upper[k-2] , upper[k-1] , p[i]) >= 0)
            k--;
        lower[j++] = p[i];
        upper[k++] = p[i];
    }
    lower.resize(j);
    upper.resize(k);
}
int main(){

    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        vector<point> v;
        int x , y;
        for(int i = 0 ; i < n ; i++){
            scanf("%d%d",&x , &y);
            v.pb(point(x , y , i+1));
        }
        vector<point> lower , upper;
        convex_hull(v , upper , lower);
        for(int i = upper.size() - 2 ; i > 0 ; i--)
            lower.pb(upper[i]);
        double dist = 0.0;
        for(int i = 1 ; i < lower.size() ; i++)
            dist += lower[i-1].distance(lower[i]);
        dist += lower[lower.size() -1].distance(lower[0]);
        printf("%.2lf\n", dist);
        for(int i = 0 ; i < lower.size() ; i++)
            printf("%d ", lower[i].pos);
        printf("\n");
    }

    return 0;
}