Pagini recente » Cod sursa (job #264830) | Cod sursa (job #3148145) | Cod sursa (job #2215046) | Cod sursa (job #2929947) | Cod sursa (job #2636748)
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
FILE* fin, * fout;
struct point {
double x, y;
};
vector<point> v;
vector<int> 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;
}
double dist(point a, point b) {
double x = a.x - b.x, y = a.y - b.y;
x *= x;
y *= y;
return x + y;
}
int find_left_most() {
int i = 0;
for(int j=1;j<v.size();++j)
if(v[j].x<v[i].x || (v[j].x==v[i].x && v[j].y<v[i].y))
i=j;
return i;
}
void convex_hull() {
int start = find_left_most();
poly.push_back(start);
bool done = false;
int current = start, next = (start + 1) % v.size();
while (!done) {
for (int i = 0;i < v.size();++i) {
if (i == current || i == next) continue;
int s = side(v[current], v[next], v[i]);
if (s > 0)
next = i;
else if (s == 0) {
if (dist(v[current], v[i]) > dist(v[current], v[next]))
next = i;
}
}
if (next == poly[0])
done = true;
else {
poly.push_back(next);
current = next;
next = 0;
}
}
fprintf(fout,"%i\n", poly.size());
reverse(poly.begin() + 1, poly.end());
for(int i:poly)
fprintf(fout,"%lf %lf\n",v[i].x,v[i].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;
}