Pagini recente » Cod sursa (job #36376) | Cod sursa (job #2947339) | Cod sursa (job #1106429) | Cod sursa (job #2869289) | Cod sursa (job #2631589)
#include <bits/stdc++.h>
using namespace std;
#define NMAX 120005
struct point {
double x, y;
} v[NMAX], c;
int n, Stack[NMAX], cnt;
int crossProduct(point a, point b, point c) {
double cross = (a.x * b.y) - (a.y * b.x) + (b.x * c.y) - (b.y * c.x) + (c.x * a.y) - (c.y * a.x);
if(cross > 0) return 1;
if(!cross ) return 0;
return -1;
}
bool cmp(point a, point b) {
if(a.x == c.x && a.y == c.y) {
return true;
} else if(b.x == c.x && b.y == c.y) {
return false;
}
return crossProduct(a, b, c) > 0;
}
void read() {
scanf("%d%lf%lf", &n, &c.x, &c.y);
v[1] = c;
for(int i = 2; i <= n; ++i) {
scanf("%lf%lf", &v[i].x, &v[i].y);
if((v[i].x == c.x && v[i].y < c.y) || (v[i].x < c.x)) {
c = v[i];
}
}
}
void solve() {
sort(v + 1, v + 1 + n, cmp);
for(int i = 1; i <= n; ++i) {
while(cnt >= 2 && crossProduct(v[Stack[cnt - 1]], v[Stack[cnt]], v[i]) <= 0) {
--cnt;
}
Stack[++cnt] = i;
}
}
void print() {
printf("%d\n", cnt);
for(int i = 1; i <= cnt; ++i) {
printf("%lf %lf\n", v[Stack[i]].x, v[Stack[i]].y);
}
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
read();
solve();
print();
return 0;
}