Pagini recente » Cod sursa (job #61846) | Cod sursa (job #2117789) | Cod sursa (job #2866664) | Cod sursa (job #1133241) | Cod sursa (job #2106868)
#include <bits/stdc++.h>
#define NMAX 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct{double x,y;};
Punct points[NMAX];
Punct st[NMAX];
inline double determ(const Punct& A, const Punct& B, const Punct& C)
{
return A.x*B.y + B.x*C.y + A.y*C.x - C.x*B.y - A.x*C.y - B.x*A.y;
}
inline bool cmp(const Punct& p1, const Punct& p2)
{
return determ(points[1], p1, p2) < 0;
}
int main()
{
int n;
double x,y;
fin>>n;
for(int i=1;i<=n;i++)
{
fin>>x>>y;
points[i] = Punct{x,y};
}
for(int i=2;i<=n;i++)
{
if( (points[i].x < points[1].x ) || (points[i].x == points[1].x && points[i].y < points[1].x) )
{
swap(points[1], points[i]);
}
}
sort(points+2, points+n+1, cmp);
st[1] = points[1];
st[2] = points[2];
int head = 2;
for(int i=3;i<=n;i++)
{
while(head > 2 && determ(st[head-1], st[head], points[i]) > 0)
head--;
st[++head] = points[i];
}
fout << fixed;
fout << head << '\n';
for(int i = head; i > 0 ; i--)
{
fout << setprecision(9) << st[i].x << ' ' << st[i].y << '\n';
}
return 0;
}