Pagini recente » Cod sursa (job #1807393) | Cod sursa (job #3234030) | Cod sursa (job #1327242) | Cod sursa (job #833237) | Cod sursa (job #1956219)
#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;
pair<double,double> a[120005];
vector <int> p;
bool comp(pair<double,double> n, pair<double,double> m){
return (n.x-a[1].x)*(m.y-a[1].y)-(n.y-a[1].y)*(m.x-a[1].x)>0;
}
int main(){
ios_base :: sync_with_stdio(0);
in >> n;
a[0]={1e9+5,1e9+5};
for(int i=1;i<=n;i++) {
in >> a[i].x >> a[i].y;
if(a[i].x<a[bst].x) bst=i;
else if(a[i].x==a[bst].x && a[i].y<a[bst].y) bst=i;
}
swap(a[1],a[bst]);
sort(a+2,a+n+1,comp);
//for(int i=1;i<=n;i++) cout << a[i].x << ' ' << a[i].y << '\n';
//for(int i=1;i<=n;i++) cout << a[i].x << ' ';
p.pb(1); p.pb(2); int t=1;
for(int i=3;i<=n;i++){
while(((a[p[t]].x-a[p[t-1]].x)*(a[i].y-a[p[t-1]].y)-(a[p[t]].y-a[p[t-1]].y)*(a[i].x-a[p[t-1]].x))<=0) p.pop_back(),t--;
p.pb(i); t++;
}
out << t+1 << '\n';
for(int i : p) out << fixed << setprecision(6) << a[i].x << ' ' << a[i].y << '\n';
}