Pagini recente » Cod sursa (job #2670423) | Cod sursa (job #1397287) | Cod sursa (job #869121) | Cod sursa (job #223933) | Cod sursa (job #559153)
Cod sursa(job #559153)
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define maxn 120010
#define pii pair<double, double>
#define x first
#define y second
int N, top;
int stiva[2 * maxn];
pii P[maxn];
vector<pii> sol;
int cmp(pii a, pii b) {
if(a.x != b.x) return a.x < b.x;
return a.y < b.y;
}
double produs(pii p1, pii p2, pii p3) {
double A = p1.y - p2.y;
double B = p2.x - p1.x;
double C = p1.x * p2.y - p1.y * p2.x;
return A * p3.x + B * p3.y + C;
}
int main() {
FILE *f1=fopen("infasuratoare.in", "r"), *f2=fopen("infasuratoare.out", "w");
int i, j;
fscanf(f1, "%d\n", &N);
for(i=1; i<=N; i++) {
fscanf(f1, "%lf %lf\n", &P[i].x, &P[i].y);
}
sort(P+1, P+N+1, cmp);
top ++; stiva[top] = 1;
top ++; stiva[top] = 2;
for(i=3; i<=N; i++) {
while(top > 1 && produs(P[ stiva[top-1] ], P[ stiva[top] ], P[i]) < 0) {
top --;
}
top ++; stiva[top] = i;
}
for(i=1; i<=top; i++) {
sol.push_back(P[ stiva[i] ]);
}
top = 1; stiva[top] = N;
top = 2; stiva[top] = N - 1;
for(i=N-2; i>=1; i--) {
while(top > 1 && produs(P[ stiva[top-1] ], P[ stiva[top] ], P[i]) < 0) {
top --;
}
top ++; stiva[top] = i;
}
for(i=2; i<top; i++) {
sol.push_back(P[ stiva[i] ]);
}
fprintf(f2, "%d\n", sol.size());
for(i=0; i<sol.size(); i++) {
fprintf(f2, "%lf %lf\n", sol[i].x, sol[i].y);
}
fclose(f1); fclose(f2);
return 0;
}