Pagini recente » Cod sursa (job #1991806) | Cod sursa (job #2624946) | Cod sursa (job #2624943) | Cod sursa (job #951671) | Cod sursa (job #720384)
Cod sursa(job #720384)
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct point
{
double x,y;
};
typedef vector<point>::iterator v_it;
bool lower_y(point &a, point &b)
{
if (a.y<b.y) return 1;
else if (a.y==b.y) return a.x<b.x;
else return 0;
}
struct lower_angle
{
point orig;
lower_angle(point O)
{
orig=O;
}
bool operator()(point a, point b)
{
a.x-=orig.x;a.y-=orig.y;
b.x-=orig.x;b.y-=orig.y;
return a.y*b.x<a.x*b.y;
}
};
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int nP; scanf("%d",&nP);
vector<point> vP;
for (int i=1;i<=nP;i++)
{
point tmp;
scanf("%lf%lf",&tmp.x,&tmp.y);
vP.push_back(tmp);
}
v_it pTmp=min_element(vP.begin(),vP.end(),lower_y);
point orig=*pTmp; vP.erase(pTmp);
sort(vP.begin(),vP.end(),lower_angle(orig));
vector<point> sol;
sol.push_back(orig); sol.push_back(vP.front());
for (v_it it=vP.begin()+1;it!=vP.end();++it)
{
while (!lower_angle(*(sol.end()-2))(sol.back(),*it))//right cw turn
sol.pop_back();
sol.push_back(*it); it++;
}
printf("%d\n",sol.size());
for (int i=0;i<sol.size();i++) printf("%lf %lf\n",sol[i].x,sol[i].y);
return 0;
}