Pagini recente » Cod sursa (job #875540) | Cod sursa (job #2559177) | Cod sursa (job #525480) | Cod sursa (job #1810996) | Cod sursa (job #2462723)
#include <bits/stdc++.h>
using namespace std;
int n;
struct p{
double x,y;};
vector<p> v,sol;
#define EPS 1e-12
double cp(p p1, p p2, p p3){
return (p2.x-p1.x)*(p3.y-p1.y) - (p2.y-p1.y)*(p3.x-p1.x);
}
double cmp(p p1, p p2){
return (cp(v[0],p1,p2)>0);
}
void sortare()
{
int imin=0;
p pmin =v[0];
for(int i=0;i<n;i++){
if(v[i].y < pmin.y)
imin=i,pmin=v[i];
else if(v[i].y == pmin.y && v[i].x < pmin.x)
imin=i,pmin=v[i];
}
swap(v[0],v[imin]);
sort(v.begin()+1,v.end(),cmp);
}
void convexhull(){
sol.push_back(v[0]);
sol.push_back(v[1]);
int ssol = 2;
for(int i=2;i<n;i++){
while(ssol>=2 && cp(sol[ssol-2],sol[ssol-1],v[i])<EPS)
{
sol.pop_back();
ssol--;
}
sol.push_back(v[i]);
ssol++;
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
cin>>n;
double x,y;
p pnct;
for(int i=0;i<n;i++)
{
cin>>x>>y;
pnct.x=x,pnct.y=y;
v.push_back(pnct);
}
sortare();
convexhull();
cout<<sol.size()<<"\n"<<setprecision(6)<<fixed;
for(int i=0;i<sol.size();i++)
cout<<sol[i].x<< " "<<sol[i].y<<"\n";
}