Pagini recente » Cod sursa (job #785289) | Cod sursa (job #2918341) | Cod sursa (job #2595948) | Cod sursa (job #1340449) | Cod sursa (job #3301109)
#include <algorithm>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <iostream>
#define MAX 100099
#define W 1000000000.0
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
typedef struct Point {
double x, y, deg;
};
Point points[MAX], o = {W, W, 0.0}, stack[MAX];
int n, dim = 0;
double calc(Point a, Point b) {
return atan2(a.y - b.y, a.x - b.x);
}
bool checkOrigin(Point p) {
if (p.y < o.y)
return true;
if (p.y == o.y && p.x < o.x)
return true;
return false;
}
bool cmp(Point a, Point b) {
if (a.deg == b.deg) {
double d1 = (a.x - o.x) * (a.x - o.x) + (a.y - o.y) * (a.y - o.y);
double d2 = (b.x - o.x) * (b.x - o.x) + (b.y - o.y) * (b.y - o.y);
return d1 > d2;
}
return a.deg < b.deg;
}
bool left(Point a, Point b, Point c) {
double prd = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
return prd > 0;
}
void read() {
f >> n;
for (int i = 0; i < n; i++) {
f >> points[i].x >> points[i].y;
points[i].deg = 0.0;
if (checkOrigin(points[i])) {
o = points[i];
}
}
for (int i = 0; i < n; i++) {
points[i].deg = calc(points[i], o);
}
sort(points, points + n, cmp);
int j = 0;
for (int i = 1; i < n; i++) {
if (fabs(points[i].deg - points[j].deg) > 1e-9) {
points[++j] = points[i];
}
}
n = j + 1;
}
void print(Point p) {
g << fixed << setprecision(6) << p.x << " " << p.y << '\n';
}
void solve() {
stack[0] = points[0];
dim = 1;
if (n > 1) {
stack[1] = points[1];
dim++;
}
for (int i = 2; i < n; i++) {
while (dim >= 2 && !left(stack[dim - 2], stack[dim - 1], points[i])) {
dim--;
}
stack[dim++] = points[i];
}
g << dim << '\n';
for (int i = 0; i < dim; i++) {
print(stack[i]);
}
}
int main() {
read();
solve();
return 0;
}