Pagini recente » Cod sursa (job #1398100) | Cod sursa (job #467468) | Cod sursa (job #706397) | Cod sursa (job #306932) | Cod sursa (job #1969830)
#include <fstream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <stack>
#include <iomanip>
#include <queue>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define nmax 120010
struct punct
{
long double x,y;
} v[nmax],stk[nmax],minim;
int n,i,vf;
long double cp(punct A, punct B, punct C)
{
return (B.y-A.y)*(C.x-A.x)-(C.y-A.y)*(B.x-A.x);
}
class cmp
{
public:
bool operator()(punct A, punct B)
{
return cp(v[1],A,B)<0;
}
};
int main()
{
fin >> n;
minim.x=1000000100;
int poz;
for (i=1; i<=n; i++)
{
fin >> v[i].x >> v[i].y;
if (v[i].x<minim.x||(v[i].x==minim.x&&v[i].y<minim.y))
minim=v[i],poz=i;
}
swap(v[1],v[poz]);
sort(v+2,v+n+1,cmp());
stk[++vf]=v[1];
stk[++vf]=v[2];
for (i=3; i<=n; i++)
{
while (vf>0&&cp(stk[vf-1],stk[vf],v[i])>0)
vf--;
stk[++vf]=v[i];
}
fout << vf << '\n';
for (i=1; i<=vf; i++)
fout << fixed << setprecision(12) << stk[i].x << ' ' << stk[i].y << '\n';
}