Pagini recente » Cod sursa (job #448186) | Cod sursa (job #20629) | Cod sursa (job #769460) | Cod sursa (job #2106904) | Cod sursa (job #3159211)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point {
double x, y;
};
enum Orientation {
COLINEAR,
CLOCKWISE,
COUNTER_CLOCKWISE
};
Orientation calculateOrientation(Point p1, Point p2, Point p3) {
double det = (p2.x - p1.x) * (p3.y - p1.y) -
(p3.x - p1.x) * (p2.y - p1.y);
if (det > 0) return CLOCKWISE;
else if (det < 0) return COUNTER_CLOCKWISE;
else return COLINEAR;
}
Point points[120005], poligon[120005];
int length, poligonLength;
void buildPoligonTop() {
for (int i = 0; i < length; i++) {
while (poligonLength >= 2 &&
calculateOrientation(poligon[poligonLength - 2],
poligon[poligonLength - 1],
points[i]) != CLOCKWISE)
poligonLength--;
poligon[poligonLength++] = points[i];
}
}
void buildPoligonBottom() {
for (int i = length - 3; i >= 0; i--) {
while (poligonLength >= 2 &&
calculateOrientation(poligon[poligonLength - 2],
poligon[poligonLength - 1],
points[i]) != CLOCKWISE)
poligonLength--;
poligon[poligonLength++] = points[i];
}
}
int main() {
fout << fixed << setprecision(6);
fin >> length;
for (int i = 0; i < length; i++)
fin >> points[i].x >> points[i].y;
sort(points, points + length, [](Point p1, Point p2) {
return p1.x == p2.x ? p1.y > p2.y : p1.x < p2.x;
});
buildPoligonTop();
buildPoligonBottom();
poligonLength--;
fout << poligonLength << "\n";
for (int i = 0; i < poligonLength; i++)
fout << poligon[i].x << " " << poligon[i].y << "\n";
}