Pagini recente » Cod sursa (job #1088225) | Cod sursa (job #1727597) | Cod sursa (job #2720124) | Cod sursa (job #1591807) | Cod sursa (job #270313)
Cod sursa(job #270313)
#include<stdio.h>
#include<algorithm>
using namespace std;
#define N 120001
#define INF 2000000000
int u, n, ind[N];
struct coord{double x, y;} a[N], q[N], aux, mi;
void citire(), rezolva();
double pvect(double x1, double y1, double x2, double y2, double x3, double y3){
return ((double)(x1*y2 + x2*y3 + x3*y1) > (double)(x3*y2 + y3*x1 + x2*y1));
}
inline bool cmp(int j, int i){ return pvect(a[i].x, a[i].y, mi.x, mi.y, a[j].x, a[j].y);}
int main (){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
citire();
int i;
u = 2;
for (i = 2; i <= n; i++){
while (!pvect(q[u-2].x, q[u-2].y, q[u-1].x, q[u-1].y, a[ind[i]].x, a[ind[i]].y)) u--;
q[u++] = a[ind[i]];
}
for (i = 0 ; i < u; i++ )
printf("%.6lf %.6lf\n", q[i].x, q[i].y);
return 0;
}
void citire(){
scanf("%d ", &n); mi.x = INF; mi.y = INF;
int i, ct;
for (i = 1; i <= n; i++){
scanf("%lf %lf", &a[i].x, &a[i].y); ind[i] = i;
if (a[i].x < mi.x || (a[i].x == mi.x && a[i].y < mi.y))
mi.x = a[i].x, mi.y = a[i].y, ct = i;
}
aux = a[ct]; a[ct] = a[n]; a[n] = aux;
q[0] = mi;
sort(ind + 1, ind + n, cmp);
q[1] = a[ind[1]];
}