Pagini recente » Cod sursa (job #2293730) | Cod sursa (job #2965586) | Cod sursa (job #2892065) | Cod sursa (job #813953) | Cod sursa (job #518985)
Cod sursa(job #518985)
#include<stdio.h>
#include<algorithm>
#define inf "infasuratoare.in"
#define outf "infasuratoare.out"
#define NMax 121000
#define INF 0x3f3f3f3f
using namespace std;
struct punct { double x,y; };
int N;
punct A[NMax], S[NMax], P0; int vf;
void read()
{
scanf("%d",&N);
punct p; double x,y;
for(int i=1; i<=N; i++)
{
scanf("%lf%lf",&x,&y); p.x=x; p.y=y;
A[i] = p;
}
}
struct cmp
{
bool operator () (const punct &a, const punct &b)
{
return ( (double)( ( a.x - P0.x )*( b.y - P0.y) - ( b.x - P0.x )*( a.y - P0.y ) ) > 0 );
}
};
bool turn_left(punct a, punct b, punct c)
{
return ( (double)( (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y) ) > 0 );
}
void solve()
{
int minX = INF, minY = INF;
for(int i=1; i<=N; i++) {
if( A[i].y < minY ) P0 = A[i], minY = P0.y, minX = P0.x;
else if( A[i].y == minY && A[i].x < minX ) P0 = A[i], minX = P0.x; }
sort( A+1, A+N+1, cmp() );
S[++vf] = A[1]; S[++vf] = A[2];
for(int i=3; i<=N; i++)
{
while( vf>=2 !turn_left( S[vf-1], S[vf], A[i] ) ) vf--;
S[++vf] = A[i];
}
printf("%d\n",vf);
for(int i=1; i<=vf; i++) printf("%lf %lf\n", S[i].x, S[i].y);
//for(int i=1; i<=N; i++) printf("%lf %lf\n", A[i].x, A[i].y);
}
int main()
{
freopen(inf,"r",stdin); freopen(outf,"w",stdout);
read(); solve();
return 0;
}