Pagini recente » Cod sursa (job #2475692) | Cod sursa (job #2953308)
#include <bits/stdc++.h>
using namespace std;
#define MAX_N 120000
struct Point { double x, y; };
int noPoints;
Point points[MAX_N];
vector<Point> convexHull;
int findStartPoint() {
int startIndex, i;
startIndex = 0;
for (i = 1; i < noPoints; ++i)
if (points[i].y < points[startIndex].y ||
(points[i].y == points[startIndex].y && points[i].x < points[startIndex].x))
startIndex = i;
return startIndex;
}
inline double orientation(const Point& a, const Point& b, const Point& c) {
return (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
}
inline bool cmpPoint(const Point& a, const Point& b) {
return orientation(points[0], a, b) < 0;
}
void computeHull() {
int i;
convexHull.push_back(points[0]);
convexHull.push_back(points[1]);
for (i = 2; i < noPoints; ++i) {
while (convexHull.size() >= 2 && orientation(convexHull[convexHull.size() - 2], convexHull.back(), points[i]) >= 0)
convexHull.pop_back();
convexHull.push_back(points[i]);
}
}
int main() {
FILE *fin, *fout;
fin = fopen("infasuratoare.in", "r");
fout = fopen("infasuratoare.out", "w");
int i;
fscanf(fin, "%d", &noPoints);
for (i = 0; i < noPoints; ++i)
fscanf(fin, "%lf%lf", &points[i].x, &points[i].y);
swap(points[0], points[findStartPoint()]);
sort(points + 1, points + noPoints, cmpPoint);
computeHull();
fprintf(fout, "%llu\n", convexHull.size());
for (const Point& p : convexHull)
fprintf(fout, "%lf %lf\n", p.x, p.y);
fclose(fin);
fclose(fout);
return 0;
}