Pagini recente » Cod sursa (job #1749749) | Cod sursa (job #884741) | Cod sursa (job #641937) | Cod sursa (job #2293925) | Cod sursa (job #2233842)
#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;
bool comp(pld a, pld b){
int p,q;
if(a.x==x) p=0;
else if(a.x<x) p=1;
else p=-1;
if(b.x==x) q=0;
else if(b.x<x) q=1;
else q=-1;
if(p!=q) return p<q;
else if(p==0) return a.y<b.y;
else return (a.y-y)/(a.x-x)<(b.y-y)/(b.x-x);
}
ld det(ll a, ll b, ll c, ll d, ll e, ll f, ll g, ll h, ll i){
return a*e*i+b*f*g+c*d*h-c*e*g-f*h*a-i*b*d;
}
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(det(x.x,x.y,1,y.x,y.y,1,z.x,z.y,1)<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';
}
}