Pagini recente » Cod sursa (job #1187010) | Cod sursa (job #2305856) | Cod sursa (job #2938376) | Cod sursa (job #1138574) | Cod sursa (job #1826554)
#include<cstdio>
#include<algorithm>
using namespace std;
const double eps = 1.e-12;
const int NMAX = 120100;
const double inf = 1.e9 + 1;
struct Point {
double x, y;
};
double panta(Point x, Point y){
if(y.x == x.x)
return inf;
return (y.y - x.y) / (y.x - x.x);
}
int cadran(Point x, Point y){
Point ty;
ty.x = y.x - x.x;
ty.y = y.y - x.y;
if(ty.x >= 0 && ty.y > 0)
return 1;
else if(ty.x < 0 && ty.y >= 0)
return 2;
else if(ty.x <= 0 && ty.y < 0)
return 3;
else if(ty.x > 0 && ty.y <= 0)
return 4;
}
Point gl_LL;
int cmp(Point x, Point y){
if(panta(gl_LL, x) - panta(gl_LL, y) < eps)
return 1;
return 0;
}
int solve(Point *p, int *sol, int n){
int LL = 1;
for(int i = 1; i <= n; i++){
if(p[i].y < p[LL].y)
LL = i;
else if(p[i].y == p[LL].y && p[i].x < p[LL].x)
LL = i;
}
swap(p[LL], p[1]);
gl_LL = p[1];
int q1 = 0, q2 = 0;
Point c1[NMAX], c2[NMAX];
for(int i = 2; i <= n; i++)
if(panta(gl_LL, p[i]) < 0)
c2[++q2] = p[i];
else
c1[++q1] = p[i];
sort(c1 + 1, c1 + q1 + 1, cmp);
sort(c2 + 1, c2 + q2 + 1, cmp);
for(int i = 2; i <= q1 + 1; i++)
p[i] = c1[i - 1];
for(int i = q1 + 2; i <= q1 + q2 + 1; i++)
p[i] = c2[i - q1 - 1];
int cr = 1;
sol[cr++] = 1;
sol[cr] = 2;
bool b;
for(int i = 3; i <= n; i++){
b = 1;
while(b){
/*while((cadran(p[sol[cr - 1]], p[sol[cr]]) > cadran(p[sol[cr]], p[i])) &&
(panta(p[sol[cr - 1]], p[sol[cr]]) - panta(p[sol[cr]], p[i]) > eps))*/
if((cadran(p[sol[cr - 1]], p[sol[cr]]) < cadran(p[sol[cr]], p[i])))
b = 0;
else if( (cadran(p[sol[cr - 1]], p[sol[cr]]) == cadran(p[sol[cr]], p[i]))&& (panta(p[sol[cr - 1]], p[sol[cr]]) - panta(p[sol[cr]], p[i]) < -eps))
b = 0;
if(b) cr--;
}
cr++;
sol[cr] = i;
}
return cr;
}
int main(){
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int v[NMAX], n, x;
double tx, ty;
Point p[NMAX];
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%lf%lf", &tx, &ty);
p[i].x = tx;
p[i].y = ty;
}
x = solve(p, v, n);
printf("%d\n", x);
for(int i = 1; i <= x; i++){
tx = p[v[i]].x;
ty = p[v[i]].y;
printf("%.6lf %.6lf\n", tx, ty);
}
return 0;
}