Pagini recente » Cod sursa (job #546978) | Cod sursa (job #2822192) | Cod sursa (job #2799174) | Cod sursa (job #2569028) | Cod sursa (job #270153)
Cod sursa(job #270153)
#include<stdio.h>
#define N 120001
#define INF 2000000000
int u, n;
struct coord{double x, y;} a[N], q[N], aux, min;
void citire(), rezolva();
double pvect(double x1, double y1, double x2, double y2, double x3, double y3){
return (x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x1 * y3 - x2 * y1);
}
int main (){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
citire();
for ( u = 0; q[u].x != q[0].x || q[u].y != q[0].y || !u; )
rezolva();
int i;
printf("%d\n", u);
for (i = 0; i < u; i++)
printf("%.6lf %.6lf\n", q[i].x, q[i].y);
return 0;
}
void citire(){
scanf("%d ", &n); min.x = INF; min.y = INF;
int i;
for (i = 1; i <= n; i++){
scanf("%lf %lf", &a[i].x, &a[i].y);
if (a[i].x < min.x || (a[i].x == min.x && a[i].y < min.y))
min.x = a[i].x, min.y = a[i].y;
}
q[0].x = min.x; q[0].y = min.y;
}
void rezolva(){
int i;
for (i = 2;i <= n; i++){
if (a[i].x == q[u].x && a[i].y == q[u].y) continue;
if (pvect(q[u].x, q[u].y, a[1].x, a[1].y, a[i].x, a[i].y)<0){
aux = a[1];
a[1] = a[i];
a[i] = aux;
}
}
q[++u] = a[1];
aux = a[1]; a[1] = a[2]; a[2] = aux;
}