Pagini recente » Cod sursa (job #2587148) | Cod sursa (job #3136848) | Cod sursa (job #2090476) | Cod sursa (job #2552327) | Cod sursa (job #909900)
Cod sursa(job #909900)
#include <cstdio>
#include <algorithm>
#define NMAX 120002
#define INF (1 << 30)
using namespace std;
struct punct
{
double x;
double y;
double p;
}a[NMAX];
int n;
int poz;
int h = 2;
int q[NMAX];
bool cmp(punct a, punct b)
{
return a.p < b.p;
}
double panta(double x, double y)
{
if(x == 0)
return INF;
return y / x;
}
void read()
{
int xmin = INF;
int ymin = INF;
freopen("infasuratoare.in", "r", stdin);
scanf("%d\n", &n);
for(int i = 0; i < n; ++ i)
{
scanf("%lf %lf\n", &a[i].x, &a[i].y);
a[i].p = panta(a[i].x, a[i].y);
if(a[i].x < xmin || a[i].x == xmin && a[i].y < ymin)
{
poz = i;
xmin = a[i].x;
ymin = a[i].y;
}
}
swap(a[poz], a[n - 1]);
-- n;
}
double det(punct a, punct b, punct c)
{
return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y;
}
void solve()
{
q[0] = n;
q[1] = 0;
for(int i = 1; i < n; ++ i)
{
while(det(a[q[h - 2]], a[q[h - 1]], a[i]) < 0)
-- h;
q[h ++] = i;
}
}
void write()
{
freopen("infasuratoare.out", "w", stdout);
printf("%d\n", h);
for(int i = 0; i < h; ++ i)
printf("%lf %lf\n", a[q[i]].x, a[q[i]].y);
}
int main()
{
read();
sort(a, a + n, cmp);
solve();
write();
return 0;
}