Pagini recente » Cod sursa (job #937893) | Cod sursa (job #3282464) | Cod sursa (job #236158) | Cod sursa (job #1711031) | Cod sursa (job #3288857)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
#define MAXN 120000
struct point{
double x,y;
bool operator==(point a){
return (this->x==a.x&&this->y==a.y);
}
};
vector<point> convexpts,points;
stack<point> stiva;
int area(point a,point b,point c){
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
vector<point> convex(vector<point> pts){
sort(pts.begin(),pts.end(),[](point a,point b){
return (a.x==b.x)?(a.y<b.y):(a.x<b.x);
});
stack<point> lower,upper;
//Compute the lower points
for(auto pt:pts){//begin from the lowest
point top=pt,nexttop=pt;
while(lower.size()>1&&area(nexttop,top,pt)<=0){
top=lower.top();
lower.pop();
nexttop=lower.top();
}
if(area(nexttop,top,pt)>0){
lower.push(top);
}
lower.push(pt);
}
//Compute the upper points
for(int i=pts.size()-1;i>=0;i--){//begin from the greatest
point pt=pts[i],top=pt,nexttop=pt;
while(upper.size()>1&&area(nexttop,top,pt)<=0){
top=upper.top();
upper.pop();
nexttop=upper.top();
}
if(area(nexttop,top,pt)>0){
upper.push(top);
}
upper.push(pt);
}
//Combine the 2 sides
vector<point> rez;
while(!lower.empty()){
rez.push_back(lower.top());
lower.pop();
}
while(!upper.empty()){
rez.push_back(upper.top());
upper.pop();
}
//Remove the duplicates
sort(rez.begin(),rez.end(),[](point a,point b){
return (a.x==b.x)?(a.y<b.y):(a.x<b.x);
});
rez.erase(unique(rez.begin(),rez.end()),rez.end());
return rez;
}
int main(){
int n,i;
double x,y;
cin>>n;
for(i=0;i<n;i++){
cin>>x>>y;
points.push_back({x,y});
}
convexpts=convex(points);
cout<<convexpts.size()<<"\n";
for(auto pt:convexpts){
cout<<fixed<<setprecision(6)<<pt.x<<" "<<pt.y<<"\n";
}
return 0;
}