Pagini recente » Cod sursa (job #343356) | Cod sursa (job #1094943) | Cod sursa (job #2070025) | Cod sursa (job #2847849) | Cod sursa (job #2233848)
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pd pair<double,double>
#define ld long double
#define pld pair<ld,ld>
#define lg length()
#define sz size()
#define pb push_back
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005
#define x1 xdddddddddddddddddd
#define y1 ydddddddddddddddddd
int n,id;
pld a[120005];
ld x,y=LINF;
ld cp(pld a, pld b, pld c){
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool comp(pld x, pld y){
return cp(a[1],x,y)<0;
}
int32_t main(){
ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin >> n;
for(int i=1;i<=n;i++){
cin >> a[i].x >> a[i].y;
if(a[i].y<y) y=a[i].y,x=a[i].x,id=i;
else if(a[i].y==y && a[i].x<x) x=a[i].x,id=i;
}
swap(a[1],a[id]);
sort(a+2,a+n+1,comp);
vector <pld> p;
p.pb({x,y});
for(int i=2;i<=n;i++){
while(p.sz>1){
pld x=p[p.sz-2],y=p[p.sz-1],z=a[i];
if(cp(x,y,z)>0) p.pop_back();
else break;
}
p.pb(a[i]);
}
cout << p.sz << '\n';
cout << fixed << setprecision(13);
for(pld i : p){
cout << i.x << ' ' << i.y << '\n';
}
}