Pagini recente » Cod sursa (job #1920035) | Cod sursa (job #2187865) | Cod sursa (job #2371557) | Cod sursa (job #2168529) | Cod sursa (job #2544148)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point{
double x, y;
int poz;
bool operator<(point b){
return x==b.x?y<b.y:x<b.x;
}
point operator- (point a){
return {x-a.x, y-a.y};
}
};
double cp(point o, point a, point b){
a=a-o, b=b-o;
return a.x*b.y-a.y*b.x;
}
vector<point> hull(vector<point> v){
vector<point> sol;
for(int i=0,p=1;i>=0;i+=(p=i==(v.size()-1)?-p:p)){
while(sol.size()>=2&&cp(sol[sol.size()-2], sol[sol.size()-1], v[i])<0) sol.pop_back();
sol.push_back(v[i]);
}
sol.pop_back();
return sol;
}
int main(){
int n;
fin>>n;
vector<point> v;
for(int i=0;i<n;++i){
point x;
fin>>x.x>>x.y;
v.push_back(x);
}
v=hull(v);
fout<<v.size()<<"\n";
for(auto i:v){
fout<<fixed<<setprecision(10)<<i.x<<" "<<i.y<<"\n";
}
return 0;
}