Pagini recente » Cod sursa (job #2205344) | Cod sursa (job #1799646) | Cod sursa (job #1784985) | Cod sursa (job #3153679) | Cod sursa (job #2127263)
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define sz size()
#define x first
#define y second
#define pi pair <int, int>
#define pii pair <pi, pi>
#define vi vector <int>
const ll mod = 1e9 + 7;
const double r=45/atan(1);
int n;
pair <double, double> p[120001];
vi hull;
int orient(pi t, pi q, pi r){
double v=(q.y-t.y)*(r.x-q.x)-(r.y-q.y)*(q.x-t.x);
if(v==0) return 0;
if(v>0) return 2;
return 1;
}
int32_t main(){
ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin>>n;
int l=0;
p[0].x=INT_MAX;
for(int i=1; i<=n; i++){
cin>>p[i].x>>p[i].y;
if(p[i].x<p[l].x ||(p[i].x==p[l].x && p[i].y<p[l].y)){
l=i;
}
}
int t=l, q;
hull.pb(t);
do{
q=(t+1)%(n+1);
if(q==0) q++;
for(int i=1; i<=n; i++){
if(orient(p[t], p[i], p[q])==2) q=i;
}
hull.pb(q);
t=q;
}while(t!=l);
cout<<hull.sz-1<<'\n';
for(int i=0; i<hull.sz-1; i++){
cout<<fixed<<setprecision(12)<<p[hull[i]].x<<" "<<p[hull[i]].y<<'\n';
}
}