Pagini recente » Cod sursa (job #1325744) | Cod sursa (job #376484) | Cod sursa (job #1894576) | Cod sursa (job #2082891) | Cod sursa (job #681168)
Cod sursa(job #681168)
#include<stdio.h>
#include<algorithm>
#define maxn 120005
#define INF (1<<30)
#define mp make_pair
#define eps (1e-12)
using namespace std;
FILE*f=fopen("infasuratoare.in","r");
FILE*g=fopen("infasuratoare.out","w");
int n,i,vf;
struct _point{
double x,y;
double ctg;
}A[maxn];
struct stiva{
stiva(double first = 0,double second = 0):first(first),second(second){}
double first;
double second;
}St[maxn];
inline void swap ( _point &a , _point &b ){
_point aux = a; a = b; b = aux;
}
inline bool equal ( double a , double b ){
double dif = a - b;
if ( dif < 0 ) dif = -dif;
if ( dif < eps ) return 1;
return 0;
}
inline bool det ( double x1 , double y1 , double x2 , double y2 , double x3 , double y3 ){
double d = x1*y2 + x2*y3 + x3*y1 - y1*x2 - y2*x3 - y3*x1;
if ( d >= 0 || equal(d,0) ){
return 1;
}
return 0;
}
struct cmp{
inline bool operator () ( const _point &a , const _point &b ){
return a.ctg > b.ctg;
}
};
int main () {
fscanf(f,"%d",&n);
for ( i = 1 ; i <= n ; ++i ){
fscanf(f,"%lf %lf",&A[i].x,&A[i].y);
}
double ymin = INF,xmin; int poz;
for ( i = 1 ; i <= n ; ++i ){
if ( A[i].y < ymin ){
ymin = A[i].y; xmin = A[i].x;
poz = i;
}
}
swap(A[1],A[poz]);
for ( i = 1 ; i <= n ; ++i ){
A[i].x -= xmin; A[i].y -= ymin;
if ( i != 1 ){
A[i].ctg = A[i].x / A[i].y;
}
}
A[++n] = A[1];
sort(A+2,A+n,cmp());
for ( i = 1 ; i <= n ; ++i ){
while ( vf > 1 && det(A[i].x,A[i].y,St[vf].first,St[vf].second,St[vf-1].first,St[vf-1].second) ){
St[vf] = stiva(0.0,0.0);
--vf;
}
St[++vf] = stiva(A[i].x,A[i].y);
}
fprintf(g,"%d\n",vf-1);
for ( i = 1 ; i < vf ; ++i ){
fprintf(g,"%lf %lf\n",St[i].first+xmin,St[i].second+ymin);
}
fclose(f);
fclose(g);
return 0;
}