Pagini recente » Cod sursa (job #1810368) | Cod sursa (job #802321) | Cod sursa (job #2709199) | Cod sursa (job #1028827) | Cod sursa (job #2774224)
#include <bits/stdc++.h>
#define x first
#define y second
#define nmax 120000
using namespace std;
string prob="infasuratoare";
ifstream in(prob+".in");
ofstream out(prob+".out");
int n;
bool eval(pair<double,double> a,pair<double,double> b,pair<double,double> p){
return (b.x-a.x)*(p.y-a.y)-(p.x-a.x)*(b.y-a.y)<=0;
}
vector<pair<double,double>> infasuratoare(vector<pair<double,double>> v){
vector<pair<double,double>> res(nmax);
sort(v.begin(),v.end());
int k=0;
for(int i=0;i<n;i++){
while(k>=2&&eval(res[k-2],res[k-1],v[i]))k--;
res[k++]=v[i];
}
for(int i=n-1,t=k+1;i>0;i--){
while(k>=t&&eval(res[k-2],res[k-1],v[i-1]))k--;
res[k++]=v[i-1];
}
res.resize(k-1);
return res;
}
int main(){
vector<pair<double,double>> v;
in>>n;
double x,y;
for(int i=0;i<n;i++){
in>>x>>y;
v.push_back({x,y});
}
v=infasuratoare(v);
out<<v.size()<<'\n';
v.push_back(*v.begin());
for(int i=1;i<v.size();i++){
out<<fixed<<setprecision(6)<<v[i].x<<' '<<v[i].y<<'\n';
}
}