Pagini recente » Borderou de evaluare (job #1006952) | Cod sursa (job #2343686) | Clasament 3432 | Rating John Mali (drehab) | Cod sursa (job #323587)
Cod sursa(job #323587)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAX_N 120010
#define inf 2147000000
int n, i, j, h;
struct punct {
double x;
double y;
} V[MAX_N], Stiv[MAX_N];
void cit() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%lf %lf", &V[i].x, &V[i].y);
}
long double tangenta(punct A, punct B) {
if (A.x != B.x) return (long double) (A.y - B.y) / (A.x - B.x);
else return inf;
}
inline bool cmp(punct A, punct B) {
return (long double) tangenta(A, V[1]) < tangenta(B, V[1]);
}
long double semn(punct A, punct B, punct C) {
return (long double) A.x * B.y + B.x * C.y + C.x * A.y -
A.x * C.y - B.x * A.y - C.x * B.y;
}
void solve() {
//gasesc cel mai din stanga punct, si la egalitate cel mai de jos
V[n + 1].x = V[n + 1].y = inf;
j = n + 1;
for (i = 1; i <= n; i++)
if (V[i].x < V[j].x) j = i;
else if (V[i].x == V[j].x && V[i].y < V[j].y)
j = i;
//sortez punctele dupa tangenta cu acest punct
swap(V[1], V[j]);
sort(V + 2, V + n + 1, cmp);
//bag elementele in stiva
h = 1;
Stiv[1] = V[1];
for (i = 2; i <= n; i++) {
Stiv[++h] = V[i];
//am grija ca ultimul element adaugat sa nu fie in mijlocul infasuratorii
if (h >= 3 && semn(Stiv[h - 1], Stiv[h], Stiv[1]) < 0)
h--;
while (h >= 3 && semn(Stiv[h - 2], Stiv[h - 1], Stiv[h]) < 0) {
Stiv[h - 1] = Stiv[h];
Stiv[h].x = Stiv[h].y = 0;
h--;
}
}
}
void write() {
printf("%d\n", h);
for (i = 2; i <= h; i++)
printf("%lf %lf\n", Stiv[i].x, Stiv[i].y);
printf("%lf %lf\n", Stiv[1].x, Stiv[1].y);
}
int main() {
cit();
solve();
write();
return 0;
}