Pagini recente » Cod sursa (job #1570413) | Cod sursa (job #796509) | Cod sursa (job #865862) | Cod sursa (job #902461) | Cod sursa (job #2947541)
#include<bits/stdc++.h>
using namespace std;
string numeFisier="infasuratoare";
ifstream fin(numeFisier+".in"); ofstream fout(numeFisier+".out");
#define cin fin
#define cout fout
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
//#define int ll
int n;
pair<double, double> pr[120010];
double prod( pair<double, double> v1, pair<double, double> v2){
return v1.ft*v2.sc-v2.ft*v1.sc;
}
bool is_conv(pair<double, double> p1, pair<double, double> p2, pair<double, double> p3){
if( prod( make_pair( p2.ft-p1.ft, p2.sc-p1.sc ), make_pair( p3.ft-p1.ft, p3.sc-p1.sc ) )>=( (double) 0.000 ) ){
return true;
}
return false;
}
vector<pair<double, double>> getConvexHull(pair<double, double> pr[], int n){
sort(pr+1, pr+1+n);
vector<pair<double, double>> hull;
for(int i=1; i<=n; i++){
if(hull.size()<2){
hull.pb(pr[i]);
continue;
}
while( (hull.size()>=2) && (!is_conv( hull[hull.size()-2 ], hull[ hull.size()-1 ], pr[i] ) ) ){
hull.pop_back();
}
hull.pb(pr[i]);
}
for(int i=n-1; i>=1; i--){
if(hull.size()<2){
hull.pb(pr[i]);
continue;
}
while( (hull.size()>=2) && (!is_conv( hull[hull.size()-2 ], hull[ hull.size()-1 ], pr[i] ) ) ){
hull.pop_back();
}
hull.pb(pr[i]);
}
hull.pop_back();
return hull;
}
int32_t main(){
INIT
cin>>n;
for(int i=1; i<=n; i++){
cin>>pr[i].ft>>pr[i].sc;
}
vector<pair<double, double>> hull = getConvexHull(pr, n);
cout<<hull.size()<<"\n";
for(auto pr:hull){
cout<<fixed<<setprecision(6)<<pr.ft<<" "<<pr.sc<<"\n";
}
return 0;
}