Pagini recente » Cod sursa (job #1903079) | Cod sursa (job #2055072) | Cod sursa (job #2193252) | Cod sursa (job #1912640) | Cod sursa (job #1979112)
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <climits>
using namespace std;
typedef long long LL;
#ifdef INFOARENA
#define ProblemName "infasuratoare"
#endif
#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif
#define MAXN 120010
double x[MAXN], y[MAXN];
int pts[MAXN], N;
int S[MAXN], sindex;
inline double cross(int i, int j) {
return x[i] * y[j] - y[i] * x[j];
}
inline double cross(int i, int j, int k) {
//printf("%d %d %d -- %.2lf\n", i, j, k, cross(i, j) + cross(j, k) + cross(k, i));
return cross(i, j) + cross(j, k) + cross(k, i);
}
bool comp(int i, int j) {
return cross(pts[0], i, j) < 0;
}
void buildC() {
sindex = 0;
for (int i = 0; i < N; ++i) {
while (sindex >= 2 &&
cross(S[sindex - 2], S[sindex - 1], pts[i]) > 0)
--sindex;
S[sindex++] = pts[i];
}
}
void printC() {
printf("%d\n", sindex);
for (int i = 0; i < sindex; ++i)
printf("%lf %lf\n", x[S[i]], y[S[i]]);
}
int main() {
assert(freopen(InFile, "r", stdin));
assert(freopen(OuFile, "w", stdout));
scanf("%d", &N);
int minIndex = 0;
for (int i = 0; i < N; ++i) {
pts[i] = i;
scanf("%lf%lf", &x[i], &y[i]);
if ((x[i] < x[minIndex]) ||
(x[i] == x[minIndex] && y[i] < y[minIndex]))
minIndex = i;
}
swap(pts[0], pts[minIndex]);
sort(pts + 1, pts + N, comp);
buildC();
printC();
return 0;
}