Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<fstream>
- #include<iostream>
- #include<vector>
- #include<set>
- #define x first
- #define y second
- #define mp make_pair
- #define pb push_back
- using namespace std;
- typedef pair<int, int> pii;
- int n,a,b;
- vector<pii> T, st, st1, st2, rest;
- set<pii> QQ;
- set<pii>::iterator t;
- int v_prod(pii a, pii b, pii c){
- int abx = b.x-a.x;
- int aby = b.y-a.y;
- int bcx = c.x-b.x;
- int bcy = c.y-b.y;
- return abx*bcy - bcx*aby;
- }
- int main(){
- //ifstream cin("input.txt");ofstream cout("output.txt");
- cin>>n;
- for(int i = 0; i < n; i++) {
- cin>>a>>b;
- QQ.insert(mp(a,b));
- }
- for (t = QQ.begin(); t!=QQ.end(); t++) T.pb((*t));
- st.resize(0);
- st.pb(T[0]);
- for(int i = 1; i < T.size(); i++){
- bool flag = 1;
- while((int)st.size() > 1 && flag == 1){
- flag = 0;
- if(v_prod(st[(int)st.size()-2], st[(int) st.size()-1], T[i]) < 0)
- {
- st.pop_back();
- flag = 1;
- }
- }
- st.pb(T[i]);
- }
- st1 = st;
- st.resize(0);
- st.pb(T[0]);
- for(int i = 1; i < T.size(); i++){
- bool flag = 1;
- while((int)st.size() > 1 && flag == 1){
- flag = 0;
- if(v_prod(st[(int)st.size()-2], st[(int) st.size()-1], T[i]) > 0)
- {
- st.pop_back();
- flag = 1;
- }
- }
- st.pb(T[i]);
- }
- st2 = st;
- rest = st1;
- for(int i = st2.size()-2; i >=1; i--) rest.pb(st2[i]);
- for(int i = 0; i < rest.size(); i++) cout<<rest[i].x<<' '<<rest[i].y<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement