Pagini recente » Cod sursa (job #1504805) | Cod sursa (job #2078282) | Cod sursa (job #245044) | Cod sursa (job #125570) | Cod sursa (job #1956083)
#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<long long,long long>
#define rd(x) cin >> x;
#define rda(a,n) for(int i=1;i<=n;i++) cin >> a[i];
#define wr(x) cout << x << ' ';
#define wrl(x) cout << x << '\n';
#define wra(a,n) for(int i=1;i<=n;i++) cout << a[i] << ' '; cout << '\n';
#define lg length()
#define pb(x) push_back(x)
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005
struct comp{
bool operator()(int a, int b){
return a>b;
}
};
int n,bst;
double x[120005],y[120005];
pair<int,double> a[120005];
vector <int> p;
bool comp(pair<int,double> a, pair<int,double> b){
return a.y<b.y;
}
int main(){
ios_base :: sync_with_stdio(0);
in >> n;
x[0]=1e9+5; y[0]=1e9+5;
for(int i=1;i<=n;i++) {
in >> x[i] >> y[i];
if(x[i]<x[bst]) bst=i;
else if(x[i]==x[bst] && y[i]<y[bst]) bst=i;
}
for(int i=1;i<=n;i++){
a[i].x=i;
if(i!=bst){
if(y[i]<y[bst]) a[i].y=atan((x[i]-x[bst])/(y[bst]-y[i]));
else if(y[i]==y[bst]) a[i].y=90;
else a[i].y=180-atan((x[i]-x[bst])/(y[i]-y[bst]));
}
else{
a[i].y=1000;
}
}
sort(a+1,a+n+1,comp);
//for(int i=1;i<=n;i++) cout << a[i].x << ' ';
p.pb(bst); p.pb(a[1].x); int t=1;
for(int i=2;i<n;i++){
while(((x[p[t]]-x[p[t-1]])*(y[a[i].x]-y[p[t-1]])-(y[p[t]]-y[p[t-1]])*(x[a[i].x]-x[p[t-1]]))<=0) p.pop_back(),t--;
p.pb(a[i].x); t++;
}
out << t+1 << '\n';
for(int i : p) out << fixed << setprecision(6) << x[i] << ' ' << y[i] << '\n';
}