Pagini recente » Cod sursa (job #286549) | Cod sursa (job #2029654) | Cod sursa (job #1755562) | Cod sursa (job #2212061) | Cod sursa (job #1623844)
#include<stdio.h>
#include<algorithm>
#define DIM 120005
FILE *f=fopen("infasuratoare.in","r"), *g=fopen("infasuratoare.out","w");
using namespace std;
struct Punct{ double x, y; };
int N, hST;
Punct v[DIM], ST[DIM];
bool Arie( Punct A, Punct B, Punct C ){
double arie = A.x * B.y + B.x * C.y + C.x * A.y
- B.x * A.y - C.x * B.y - A.x * C.y;
if( arie > 0 ) return 1;
return 0;
}
bool cmp( Punct A, Punct B ){ return Arie( v[1], A, B ); }
void Citire(){
int i, iFIX;
Punct FIX;
fscanf(f,"%d\n",&N);
for(i=1;i<=N;i++){
fscanf(f,"%lf %lf\n",&v[i].x,&v[i].y);
if( i == 1 )
{ FIX = v[i]; iFIX = i; }
else if( v[i].x < FIX.x || ( v[i].x == FIX.x && v[i].y < FIX.y ) )
{ FIX = v[i]; iFIX = i; }
}
if( i != iFIX )
swap( v[1], v[iFIX] );
sort(v+2,v+N+1,cmp);
}
void Creare(){
int i;
hST = 2;
ST[1] = v[1];
ST[2] = v[2];
for(i=3;i<=N;i++){
while( Arie( ST[hST-1], ST[hST], v[i] ) == 0 && hST > 2 )
hST--;
ST[++hST] = v[i];
}
fprintf(g,"%d\n",hST);
for(i=1;i<=hST;i++)
fprintf(g,"%.6lf %.6lf\n",ST[i].x,ST[i].y);
}
int main(){
Citire();
Creare();
return 0;
}