Pagini recente » Istoria paginii utilizator/llleroiv | Cod sursa (job #1486069) | Cod sursa (job #1463899) | Cod sursa (job #359259) | Cod sursa (job #2405979)
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
FILE *fin = fopen("infasuratoare.in", "r");
FILE *fout = fopen("infasuratoare.out", "w");
#define MAXN 120000
#define EPS 0.000000000001
#define INF 1000000001
std::vector <int> st;
struct point{
double x, y;
};
point minn;
void swap(point &a, point &b) {
point aux = a;
a = b;
b = aux;
}
bool eq(double a, double b) {
if (abs(b - a) < EPS)
return 1;
return 0;
}
bool cmp(point a, point b) {
double u = (a.y - minn.y) * (b.x - minn.x);
double v = (b.y - minn.y) * (a.x - minn.x);
if (a.x == minn.x && a.y == minn.y)
return 1;
if (b.x == minn.x && b.y == minn.y)
return 0;
if(eq(u, v)) {
if (a.x <= b.x)
return 1;
return 0;
}
else if(u < v)
return 1;
return 0;
}
bool verif (point a, point b, point c) {
if (a.x < c.x)
swap(a, c);
double t = (a.y - c.y) * (b.x - minn.x) - (b.y - minn.y) * (a.x - c.x);
double s = (b.y - a.y) * (b.x - minn.x) * (a.x - c.x) - (b.y - minn.y) * (a.x - c.x) * b.x + (a.y - c.y) * (b.x - minn.x) * a.x;
if (t < 0) {
t = -t;
s = -s;
}
if (t * minn.x > s)
return 0;
if (t * b.x < s)
return 0;
return 1;
}
point p[MAXN + 1];
int main()
{
int n;
int m = 0;
fscanf(fin, "%d", &n);
p[0].x = INF;
for (int i = 1; i <= n; i++) {
double x, y;
fscanf(fin, "%lf%lf", &x, &y);
p[i].x = x;
p[i].y = y;
if (eq(x, p[m].x)) {
if (y < p[m].y)
m = i;
}
else if (x < p[m].x)
m = i;
}
minn.x = p[m].x;
minn.y = p[m].y;
std::sort(p + 1, p + n + 1, cmp);
st.push_back(1);
st.push_back(2);
for (int i = 3; i <= n; i++) {
int siz = st.size();
while (!verif(p[st[siz - 2]], p[st[siz - 1]], p[i])) {
st.pop_back();
siz--;
}
st.push_back(i);
}
int siz = st.size();
fprintf(fout, "%d\n", siz);
for (int i = 0; i < siz; i++) {
fprintf(fout, "%lf %lf\n", p[st[i]].x, p[st[i]].y);
}
return 0;
}