Pagini recente » G. pmk | Borderou de evaluare (job #1312125) | Cod sursa (job #1005666) | Rezultatele filtrării | Cod sursa (job #1242910)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define DN 120005
#define pb push_back
#define bp pop_back
#define sz size
#define x first
#define y second
using namespace std;
typedef pair<double,double> per;
int n;
per p[DN];
vector<per> st;
int id(per a,per b,per c) {
double s=b.x*c.y+c.x*a.y+a.x*b.y;
double d=a.x*c.y+c.x*b.y+b.x*a.y;
return s-d<0;
}
int main() {
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>n;
for(int i=0; i<n; ++i) f>>p[i].x>>p[i].y;
sort(p,p+n);
st.pb(p[0]); st.pb(p[1]);
for(int i=2; i<n; ++i) {
for(;st.sz() && id(st[st.sz()-2],st.back(),p[i]);st.bp());
st.pb(p[i]);
}
st.bp();
for(int i=n-1; i>=0; --i) {
for(;st.sz() && id(st[st.sz()-2],st.back(),p[i]);st.bp());
st.pb(p[i]);
}
st.bp();
g<<st.sz()<<'\n';
for(int i=0; i<st.sz(); ++i) g<<fixed<<setprecision(8)<<st[i].x<<' '<<st[i].y<<'\n';
}