Pagini recente » Cod sursa (job #2787858) | Cod sursa (job #519516) | Cod sursa (job #657744) | Cod sursa (job #1987148) | Cod sursa (job #1164420)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define FILEIN "infasuratoare.in"
#define FILEOUT "infasuratoare.out"
#define NMAX 120005
#define EPS 1e-12
struct Pct {
double x;
double y;
bool operator<(const Pct& other) const {
if (this->x == other.x)
return this->y < other.y;
return this->x < other.x;
};
};
Pct P[NMAX];
int N;
vector<int> sol;
double CrossProduct(Pct &O, Pct &A, Pct &B) {
return (O.x - A.x) * (O.y - B.y) - (O.y - A.y) * (O.x - B.x);
}
int main() {
freopen(FILEIN, "r", stdin);
freopen(FILEOUT, "w", stdout);
scanf("%d", &N);
for ( int i = 1; i <= N; i++ ) {
double x, y;
scanf("%lf %lf", &x, &y);
P[i].x = x, P[i].y = y;
}
sort(P+1, P+N+1);
sol.resize(N); int solCnt = 0;
for ( int i = 1; i <= N; i++ ) {
while (solCnt >= 2 && CrossProduct(P[sol[solCnt - 2]], P[sol[solCnt - 1]], P[i]) <= EPS)
solCnt--;
sol[solCnt++] = i;
}
int upper = solCnt + 1;
for ( int i = N; i >= 1; i-- ) {
while (solCnt >= upper && CrossProduct(P[sol[solCnt - 2]], P[sol[solCnt - 1]], P[i]) <= EPS)
solCnt--;
sol[solCnt++] = i;
}
printf("%d\n", solCnt - 1);
for ( int i = 1; i < solCnt; i++ ) {
printf("%.6lf %.6lf\n", P[sol[i]].x, P[sol[i]].y);
}
return 0;
}