Pagini recente » Cod sursa (job #1670060) | Cod sursa (job #79724) | Cod sursa (job #2046182) | Cod sursa (job #828183) | Cod sursa (job #2485375)
#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);
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
fout << fixed << setprecision(7);
fin >> n;
for(int i=1;i<=n;i++){
fin >> v[i].fr >> v[i].sc;
}
sort(v+1,v+n+1);
vector<pair<double,double>>upper;
upper.push_back(v[1]);
upper.push_back(v[2]);
for(int i=3;i<=n;i++){
if(cross(v[i],upper[upper.size()-2],upper[upper.size()-1])>=0){
while(upper.size()>=2 && cross(v[i],upper[upper.size()-2],upper[upper.size()-1])>=0){
upper.pop_back();
}
upper.push_back(v[i]);
}
else upper.push_back(v[i]);
}
int d=upper.size()+1;
upper.push_back(v[n-1]);
for(int i=n-2;i>=1;i--){
if(cross(v[i],upper[upper.size()-2],upper[upper.size()-1])>=0){
while(upper.size()>=d && cross(v[i],upper[upper.size()-2],upper[upper.size()-1])>=0){
upper.pop_back();
}
upper.push_back(v[i]);
}
else upper.push_back(v[i]);
}
upper.pop_back();
reverse(all(upper));
fout << upper.size() << '\n';
for(int i=0;i<upper.size();i++){
fout << upper[i].fr << ' ' << upper[i].sc << '\n';
}
// cout << '\n';
}