Pagini recente » Cod sursa (job #2841623) | Cod sursa (job #2271277) | Cod sursa (job #2026735) | Cod sursa (job #1934981) | Cod sursa (job #1805930)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define x first
#define y second
const int MAX = 120000;
int n;
typedef pair<double, double> puncte;
puncte v[MAX + 1], st[MAX + 1];
int top;
double cross_product(puncte a, puncte b, puncte c)
{
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool cmp(puncte a, puncte b)
{
return cross_product(v[1], a, b) < 0;
}
void sort_puncte()
{
int p = 1;
for(int i = 2; i <= n; i++)
if(v[i] < v[p])
p = i;
swap(v[1], v[p]);
sort(v + 2, v + n + 1, cmp);
}
void convex_hull()
{
sort_puncte();
st[1] = v[1];
st[2] = v[2];
top = 2;
for(int i = 3; i <= n; i++)
{
while(top >= 2 && cross_product(st[top - 1], st[top], v[i]) > 0)
top--;
st[++top] = v[i];
}
}
int main()
{
FILE *fin, *fout;
fin = fopen("infasuratoare.in", "r");
fout = fopen("infasuratoare.out", "w");
fscanf(fin, "%d", &n);
for(int i = 1; i <= n; i++)
fscanf(fin, "%lf %lf", &v[i].x, &v[i].y);
convex_hull();
fprintf(fout, "%d\n", top);
for(int i = top; i > 0; i--)
fprintf(fout, "%.9lf %.9lf\n", st[i].x, st[i].y);
return 0;
}