Pagini recente » Cod sursa (job #1497231) | Cod sursa (job #1431466) | Cod sursa (job #1770931) | Autentificare | Cod sursa (job #2953514)
#include <bits/stdc++.h>
using namespace std;
FILE *fin, *fout;
const int NMAX = 12e4;
const double EPS = 1e-12;
struct point {
double x, y;
} v[NMAX];
vector<int> hull;
int findLowestPoint(int n) {
double ymin = 1e9 + 1;
int ind = -1;
for(int i = 0; i < n; i++)
if(v[i].y < ymin) {
ymin = v[i].y;
ind = i;
}
return ind;
}
/*
(b.y - a.y) / (b.x - a.x) ? (c.y - b.y) / (c.x - b.x)
*/
bool order(point a, point b, point c) {
long double val1 = b.y - a.y;
long double val2 = c.x - b.x;
long double val3 = c.y - b.y;
long double val4 = b.x - a.x;
long double val = val1 * val2 - val3 * val4;
return (val < 0);
}
bool cmp(point a, point b) {
return order(v[0], a, b);
}
int main() {
fin = fopen("infasuratoare.in", "r");
fout = fopen("infasuratoare.out", "w");
int n;
fscanf(fin, "%d", &n);
for(int i = 0; i < n; i++) {
fscanf(fin, "%lf%lf", &v[i].x, &v[i].y);
}
swap(v[0], v[findLowestPoint(n)]);
sort(v + 1, v + n, cmp);
//for(int i = 0; i < n; i++)
//cout << v[i].x << ' ' << v[i].y << endl;
hull.push_back(0);
hull.push_back(1);
hull.push_back(2);
for(int i = 3; i < n; i++) {
while(hull.size() >= 2 && !order(v[hull[hull.size() - 2]], v[hull[hull.size() - 1]], v[i]))
hull.pop_back();
hull.push_back(i);
}
fprintf(fout, "%d\n", hull.size());
for(int i = 0; i < hull.size(); i++) {
fprintf(fout, "%lf %lf\n", v[hull[i]].x, v[hull[i]].y);
}
fclose(fin);
fclose(fout);
return 0;
}