Pagini recente » Cod sursa (job #1718300) | Cod sursa (job #2116232) | Cod sursa (job #120837) | Cod sursa (job #708239) | Cod sursa (job #720052)
Cod sursa(job #720052)
#include <fstream>
#include <algorithm>
using namespace std;
#define lung 200000
ifstream fin("infasuratoare.in");
struct point {
double x, y;
};
int n, stiva[lung];
point p[lung];
bool cmp(point a, point b) {
return (a.x - p[1].x) * (b.y - p[1].y) > (b.x - p[1].x) * (a.y - p[1].y);
}
int isLeft(int i1, int i2, int i3) {
return p[i1].x * p[i2].y + p[i2].x * p[i3].y + p[i3].x * p[i1].y -
p[i1].y * p[i2].x - p[i2].y * p[i3].x - p[i3].y * p[i1].x;
}
int main() {
int i;
fin >> n;
freopen("infasuratoare.out", "w", stdout);
for (i = 1; i <= n; ++i) {
fin >> p[i].x >> p[i].y;
if (p[i].x < p[1].x || (p[i].x == p[1].x && p[i].y < p[1].y))
swap(p[1], p[i]);
}
sort(p + 2, p + n + 1, cmp);
stiva[++stiva[0]] = 1;
for (i = 2; i <= n; ++i) {
while (stiva[0] >= 2 && (isLeft(stiva[stiva[0] - 1], stiva[stiva[0]], i) < 0))
--stiva[0];
stiva[++stiva[0]] = i;
}
printf("%d\n", stiva[0]);
for (i = 1; i <= stiva[0]; ++i)
printf("%f %f\n", p[stiva[i]].x, p[stiva[i]].y);
return 0;
}