Pagini recente » Cod sursa (job #1839162) | Cod sursa (job #1826730) | Cod sursa (job #1338560) | Cod sursa (job #2940069) | Cod sursa (job #657805)
Cod sursa(job #657805)
#include<cstdio>
#include<algorithm>
#define inf 0xffffffff
using namespace std;
const int N = 120002;
int n, nn = 2, poz;
struct punct {
double x, y, p;
};
punct a[N], s[N], z;
bool cmp(punct a, punct b) {
return a.p > b.p ? false : true;
}
void citire() {
z.x = z.y = inf;
scanf("%d ", &n);
for (int i = 0; i < n; ++i) {
scanf("%lf %lf ", &a[i].x, &a[i].y);
if(a[i].x < z.x || a[i].x == z.x && a[i].y < z.y) {
z.x = a[i].x;
z.y = a[i].y;
poz = i;
}
}
a[poz] = a[n - 1];
--n;
}
void afisare() {
printf("%d\n", nn);
for (int i = 0; i < nn; ++i)
printf("%lf %lf\n", s[i].x, s[i].y);
}
void panta() {
for (int i = 0; i < n; ++i)
if (a[i].x == z.x)
a[i].p = inf;
else
a[i].p = (a[i].y - z.y) / (a[i].x - z.x);
}
bool determinant(punct a, punct b, punct c)
{
double det = a.x * b.y + a.y * c.x + b.x * c.y - a.y * b.x - b.y * c.x - c.y * a.x;
if (det >= 0)
return 1;
return 0;
}
void infasuratoare() {
s[0] = z;
s[1] = a[0];
for(int i = 1; i < n; ++i)
if (determinant(s[nn - 2], s[nn - 1], a[i]) == 1)
s[nn++] = a[i];
else {
while (determinant(s[nn - 2], s[nn - 1], a[i]) == 0)
s[--nn] = a[i];
++nn;
}
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
citire();
panta();
sort(a, a + n, cmp);
infasuratoare();
afisare();
return 0;
}