Pagini recente » Cod sursa (job #801767) | Cod sursa (job #2066069) | Cod sursa (job #319732) | Cod sursa (job #1776684) | Cod sursa (job #1369238)
#include <fstream>
#include <vector>
#include <stack>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int N, pmin=1, vf;
struct asd{ double x, y;}a[120005], st[120005];
double crossedprod(asd A, asd B, asd C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
double cmp(const asd &A, const asd &B)
{
return crossedprod(a[1], A, B)<0;
}
void convexhull()
{
st[++vf]=a[1]; st[++vf]=a[2];
for (int i=3; i<=N; ++i)
{
while (vf>=2 && crossedprod(st[vf-1], st[vf], a[i])>0)
--vf;
st[++vf]=a[i];
}
}
int main()
{
f>>N;
for (int i=1; i<=N; ++i)
{
f>>a[i].x>>a[i].y;
if (a[i].x<a[pmin].x) pmin=i;
else if (a[i].x==a[pmin].x && a[i].y<a[pmin].y)
pmin=i;
}
swap(a[1], a[pmin]);
sort(a+2, a+N+1, cmp);
convexhull();
g<<vf<<'\n'<<fixed<<setprecision(9);
for (int i=vf; i>0; --i)
g<<st[i].x<<' '<<st[i].y<<'\n';
return 0;
}