Pagini recente » Cod sursa (job #2333694) | Borderou de evaluare (job #1900540) | Cod sursa (job #123998) | Cod sursa (job #3292594) | Cod sursa (job #3288861)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <iomanip>
#include <set>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
#define MAXN 120000
struct point{
double x,y;
};
bool operator<(const point &a,const point &b){
return a.x<b.x||(a.x==b.x&&a.y<b.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;
set<point> seen;
while(!lower.empty()){
if(seen.insert(lower.top()).second){
rez.push_back(lower.top());
}
lower.pop();
}
while(!upper.empty()){
if(seen.insert(upper.top()).second){
rez.push_back(upper.top());
}
upper.pop();
}
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";
reverse(convexpts.begin(),convexpts.end());
for(auto pt:convexpts){
cout<<fixed<<setprecision(6)<<pt.x<<" "<<pt.y<<"\n";
}
return 0;
}