Pagini recente » Cod sursa (job #488347) | Cod sursa (job #530842) | Cod sursa (job #1213532) | Cod sursa (job #689769) | Cod sursa (job #2899889)
/// always:
#include <cstdio>
#include <string>
/// optional:
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
bool home = 1;
using namespace std;
typedef long double ld;
const string TASKNAME="infasuratoare";
const int N=120000+7;
int n;
struct Vec{
ld x;
ld y;
};
ld f(Vec a,Vec b) {
return (a.x-b.x)*(a.y+b.y);
}
ld f(Vec a,Vec b, Vec c) {
return f(a,b)+f(b,c)+f(c,a);
}
Vec v[N];
bool cmp(Vec x,Vec y) {
return f(v[1],x,y)>0;
}
bool sm(Vec a,Vec b) {
if(a.y!=b.y) return a.y<b.y;
return a.x<b.x;
}
signed main() {
#ifdef INFOARENA
home = 0;
#endif
///home=0;
if(!home) {
freopen((TASKNAME + ".in").c_str(), "r", stdin);
freopen((TASKNAME + ".out").c_str(), "w", stdout);
}else{
freopen ("I_am_iron_man", "r", stdin);
}
cin>>n;
for (int i=1;i<=n;i++) {
cin>>v[i].x>>v[i].y;
if(sm(v[i],v[1])) swap(v[i],v[1]);
}
sort(v+2,v+n+1,cmp);
v[n+1]=v[1];
vector<Vec> stk;
for (int i=1;i<=n+1;i++) {
while((int)stk.size()>=2&&f(stk[(int)stk.size()-2],stk[(int)stk.size()-1],v[i])<0) {
stk.pop_back();
}
stk.push_back(v[i]);
}
stk.pop_back();
cout<<(int)stk.size()<<"\n";
for (auto &p:stk){
cout<<fixed<<setprecision(6)<<p.x<<" "<<p.y<<"\n";
}
}