Pagini recente » Cod sursa (job #1297826) | Cod sursa (job #807449) | Cod sursa (job #241008) | Cod sursa (job #2795464) | Cod sursa (job #2204540)
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>
struct Point {
double x;
double y;
bool operator <(const Point& other) const {
return this->x < other.x || (this->x == other.x && this->y < other.y);
}
};
double det(const Point& a, const Point& b, const Point& c) {
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}
Point point;
bool cmp(const Point& a, const Point& b) {
return det(point, a, b) > 0;
}
int main() {
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n;
scanf("%d", &n);
Point points[1 + n];
int pozMin = 1;
for (int i = 1; i <= n; i++) {
scanf("%lf%lf", &points[i].x, &points[i].y);
if (points[i] < points[pozMin])
pozMin = i;
}
point = points[pozMin];
std::swap(points[1], points[pozMin]);
std::sort(points + 2, points + n + 1, cmp);
std::vector<Point> answer;
answer.push_back(points[1]);
answer.push_back(points[2]);
for (int i = 3; i <= n; i++) {
while (answer.size() >= 2 && det(*(answer.rbegin() + 1), *answer.rbegin(), points[i]) <= 0)
answer.pop_back();
answer.push_back(points[i]);
}
printf("%d\n", (int)answer.size());
std::vector<Point> :: iterator it;
for (it = answer.begin(); it != answer.end(); it++)
printf("%lf %lf\n", (*it).x, (*it).y);
fclose(stdin);
fclose(stdout);
return 0;
}