Pagini recente » Cod sursa (job #1694560) | Cod sursa (job #87211) | Cod sursa (job #1477857) | Cod sursa (job #487573) | Cod sursa (job #2636765)
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
FILE* fin, * fout;
struct point {
double x, y;
};
vector<point> v;
vector<point> poly;
double cross_product(point origin, point a, point b) {
double x1 = origin.x - a.x;
double x2 = origin.x - b.x;
double y1 = origin.y - a.y;
double y2 = origin.y - b.y;
return (y2 * x1 - y1 * x2);
}
int side(point origin, point end, point p) {
double prod = cross_product(origin, end, p);
if (prod > 0) return 1;
if (prod < 0) return -1;
return 0;
}
int find_bottom_most() {
int i = 0;
for(int j=1;j<v.size();++j)
if(v[j].y<v[i].y || (v[j].y==v[i].y && v[j].x<v[i].x))
i=j;
return i;
}
void swap(point& a, point& b) {
point aux = a;
a = b;
b = aux;
}
void convex_hull() {
int start = find_bottom_most();
swap(v[0], v[start]);
auto cmp = [p = v[0]](point& a, point& b){return side(p, a, b) == 1;};
sort(v.begin() + 1, v.end(), cmp);
poly.push_back(v[0]);
poly.push_back(v[1]);
poly.push_back(v[2]);
point x = v[1], y = v[2];
for (int i = 3;i < v.size();++i) {
while (side(x, y, v[i]) == -1) {
poly.pop_back();
x = poly[poly.size() - 2];
y = poly[poly.size() - 1];
}
poly.push_back(v[i]);
x = poly[poly.size() - 2];
y = poly[poly.size() - 1];
}
fprintf(fout, "%i\n", poly.size());
for (point p : poly)
fprintf(fout, "%lf %lf\n", p.x, p.y);
}
int main() {
fin = fopen("infasuratoare.in", "r");
fout = fopen("infasuratoare.out", "w");
int n;
fscanf(fin, "%i", &n);
while (n--) {
double x, y;
fscanf(fin, "%lf %lf", &x, &y);
v.push_back({ x,y });
}
convex_hull();
return 0;
}