Pagini recente » Cod sursa (job #1853068) | Cod sursa (job #2902370) | Cod sursa (job #2340620) | Cod sursa (job #2864110) | Cod sursa (job #3159093)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <climits>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point {
double x, y;
int index;
};
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[150], poligon[150];
int length, poligonLength;
void buildPoligonTop() {
for (int i = 1; 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 - 2; 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;
points[i].index = i;
}
sort(points, points + length, [](Point p1, Point p2) {
return p1.x == p2.x ? p1.y > p2.y : p1.x < p2.x;
});
poligon[poligonLength++] = points[0];
buildPoligonTop();
buildPoligonBottom();
poligonLength--;
int startIndex = 0, minim = INT_MAX;
for (int i = 0; i < poligonLength; i++)
if (poligon[i].index < minim) {
minim = poligon[i].index;
startIndex = i;
}
fout << poligonLength << "\n";
for (int i = startIndex; i < poligonLength; i++)
fout << poligon[i].x << " " << poligon[i].y << "\n";
for (int i = 0; i < startIndex; i++)
fout << poligon[i].x << " " << poligon[i].y << "\n";
}