Pagini recente » Cod sursa (job #818564) | Cod sursa (job #170242) | Cod sursa (job #2015826) | Cod sursa (job #2291331) | Cod sursa (job #2485380)
#include <bits/stdc++.h>
#define ll long long
#define all(a) (a).begin(), (a).end()
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define sz() size()
#define fr first
#define sc second
#define pb push_back
#define er erase
#define in insert
#define pi pair<int,int>
#define pii pair<pair<int,int>,int>
#define mp make_pair
#define int long long
#define rc(s) return cout<<s,0
#define rcc(s) cout<<s,exit(0)
///#define cin fin
///#define cout fout
using namespace std;
const int mod=1e9+7;
const int mod1=998244353;
const double eps=1e-12;
int n;
pair<double,double>v[120005];
double cross(pair<double,double>O,pair<double,double>A,pair<double,double>B){
return (A.fr-O.fr)*(B.sc-O.sc)-(A.sc-O.sc)*(B.fr-O.fr);
//pozitiv stanga
//negativ dreapta
}
int32_t main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cout << fixed << setprecision(6);
cin >> n;
for(int i=1;i<=n;i++){
cin >> v[i].fr >> v[i].sc;
}
sort(v+1,v+n+1);
vector<pair<double,double>>infas;
infas.push_back(v[1]);
infas.push_back(v[2]);
for(int i=3;i<=n;i++){
if(cross(v[i],infas[infas.size()-2],infas[infas.size()-1])>=0){
while(infas.size()>=2 && cross(v[i],infas[infas.size()-2],infas[infas.size()-1])>=0){
infas.pop_back();
}
infas.push_back(v[i]);
}
else infas.push_back(v[i]);
}
int d=infas.size()+1;
infas.push_back(v[n-1]);
for(int i=n-2;i>=1;i--){
if(cross(v[i],infas[infas.size()-2],infas[infas.size()-1])>=0){
while(infas.size()>=d && cross(v[i],infas[infas.size()-2],infas[infas.size()-1])>=0){
infas.pop_back();
}
infas.push_back(v[i]);
}
else infas.push_back(v[i]);
}
infas.pop_back();
reverse(all(infas));
cout << infas.size() << '\n';
for(int i=0;i<infas.size();i++){
cout << infas[i].fr << ' ' << infas[i].sc << '\n';
}
}