Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
//Código por Pedro Bignotto Racchetti
//O(nlogn)
#include<bits/stdc++.h>
using namespace std;
struct Pt {
int x, y;
Pt(int _x = 0, int _y = 0) : x(_x), y(_y) {}
Pt operator+(const Pt& o) { return Pt(x+o.x, y+o.y); } // soma de vetores
Pt operator-(const Pt& o) { return Pt(x-o.x, y-o.y); } // subtração de vetores
bool operator < (Pt o) const{ // ordena pelas abscissas e depois pelas ordenadas
if(x == o.x) return y < o.y;
return x < o.x;
}
void operator+=(const Pt& o) { x += o.x, y += o.y; } // somar vetores com o operador +=
void operator-=(const Pt& o) { x -= o.x, y -= o.y; } // subtrair vetores com o operador -=
long long dot(const Pt& o) { return 1ll*x*o.x + 1ll*y*o.y; } // dot - produto escalar
long long cross(const Pt& o) { return 1ll*x*o.y - 1ll*y*o.x; } // cross - produto vetorial
};
Pt pts[112345];
int marc[112345];
int n;
vector<Pt> conv, upper, lower;
void makeconv(){
long long it1 = 0, it2 = 0;
for(int i = 0; i < n; i++){
if(marc[i]) continue;
while(it1 >= 2 && (pts[i] - upper[it1 - 2]).cross(upper[it1 - 1] - upper[it1 -2]) < 0){
upper.pop_back();
it1--;
}
upper.push_back(pts[i]);
it1++;
while(it2 >= 2 && (pts[i] - lower[it2 - 2]).cross(lower[it2 - 1] - lower[it2 -2]) > 0){
lower.pop_back();
it2--;
}
lower.push_back(pts[i]);
it2++;
}
for(int i = 0; i < it1 - 1; i++) conv.push_back(upper[i]);
for(int i = it2 - 1; i > 0; i--) conv.push_back(lower[i]);
}
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++){
scanf("%lld %lld", &pts[i].x, &pts[i].y);
}
sort(pts, pts + n);
makeconv();
printf("%lu\n", conv.size());
for(int i = 0; i < conv.size(); i++ ){
printf("%lld %lld\n", conv[i].x, conv[i].y);
}
scanf("%d", &n);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment