Pagini recente » Cod sursa (job #202970) | Cod sursa (job #91815) | Cod sursa (job #37719) | Cod sursa (job #2171553) | Cod sursa (job #709600)
Cod sursa(job #709600)
#include<stdio.h>
#include<algorithm>
#define INF 1000000010
using namespace std;
FILE *fin=fopen("infasuratoare.in","r");
FILE *fout=fopen("infasuratoare.out","w");
int n, i, poz, k, stv[130000];
double minx, miny;
struct coord{
double x, y;
};
coord v[130000],aux;
int scoate(double x1, double y1, double x2, double y2, double x3, double y3){
long double x = ((long double)x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
if(x >= 0){
return 1;
}
return 0;
}
int cmp(coord a, coord b){
return (a.x * b.y) > (a.y * b.x);
}
int main(){
fscanf(fin,"%d",&n);
minx = INF;
miny = INF;
v[0].x = INF;
v[0].y = INF;
poz = 0;
for(i = 1 ; i <= n; i++){
fscanf(fin,"%lf %lf", &v[i].x, &v[i].y);
if(v[i].x < v[poz].x){
poz = i;
}
else
if(v[i].x == v[poz].x ){
if( v[i].y < v[poz].y ){
poz = i;
}
}
}
aux = v[poz];
v[poz]=v[1];
v[1]=aux;
minx = v[1].x;
miny = v[1].y;
for(i=1 ; i <= n ; i++ ){
v[i].x -= minx;
v[i].y -= miny;
}
sort(v+2, v+n+1, cmp);
stv[1]=1;
stv[2]=2; k = 2;
for(i=3;i<=n;i++){
while( k>=2 && scoate( v[i].x, v[i].y, v[stv[k]].x, v[stv[k]].y, v[stv[k-1]].x, v[stv[k-1]].y) ){
k--;
}
stv[++k] = i;
}
fprintf(fout,"%d\n",k);
for(i=1; i<= k; i++){
fprintf(fout,"%lf %lf\n", v[stv[i]].x + minx , v[stv[i]].y + miny );
}
fclose(fout);
fclose(fin);
return 0;
}