Pagini recente » Cod sursa (job #537803) | Cod sursa (job #445125) | Cod sursa (job #761086) | Cod sursa (job #2041403) | Cod sursa (job #1688935)
#include<cstdio>
#include<algorithm>
#define MAXN 120005
#define MAXD 1000000000
FILE *f=fopen("infasuratoare.in","r"), *g=fopen("infasuratoare.out","w");
using namespace std;
struct Punct{ double x, y; } v[MAXN], t;
int N, ST[MAXN], hST;
bool Arie( Punct A, Punct B, Punct C ){
double arie;
arie = A.x * B.y + B.x * C.y + C.x * A.y
- A.y * B.x - B.y * C.x - C.y * A.x;
if( arie > 0 )
return 1;
return 0;
}
bool cmp( Punct A, Punct B ){ return Arie( v[1], A, B ); }
void Citire(){
int i, xmin = MAXD, ymin = MAXD, imin;
fscanf(f,"%d\n",&N);
for(i=1;i<=N;i++){
fscanf(f,"%lf %lf\n",&v[i].x,&v[i].y);
if( v[i].x < xmin || ( v[i].x == xmin && v[i].y < ymin ) ){
xmin = v[i].x;
ymin = v[i].y;
imin = i;
}
}
if( imin != 1 )
swap( v[1], v[imin] );
sort(v+2,v+N+1,cmp);
}
void Rezolvare(){
int i;
ST[1] = 1;
ST[2] = 2;
hST = 2;
for(i=3;i<=N;i++){
while( !Arie( v[ ST[hST-1] ], v[ ST[hST] ], v[i] ) && hST > 2 )
hST--;
ST[++hST] = i;
}
fprintf(g,"%d\n",hST);
for(i=1;i<=hST;i++)
fprintf(g,"%.6lf %.6lf\n",v[ ST[i] ].x,v[ ST[i] ].y);
}
int main(){
Citire();
Rezolvare();
return 0;
}