Pagini recente » Cod sursa (job #549440) | Cod sursa (job #1365681) | Cod sursa (job #2116270) | Cod sursa (job #2543554) | Cod sursa (job #1838622)
#include <cstdio>
#include <algorithm>
#define NMax 120000
#define x first
#define y second
using namespace std;
typedef pair<double, double> Punct;
Punct stiva[NMax+1];
Punct v[NMax+1];
int vf,N;
double ceas_trig(Punct O, Punct A, Punct B)
{
return (A.x-O.x)*(B.y-O.y)-(A.y-O.y)*(B.x-O.x);
}
bool cmp(const Punct A, const Punct B)
{
return ( ceas_trig(v[1],A,B) > 0 );
}
void Read()
{
scanf("%d",&N);
for(int i = 1; i <= N; ++i) scanf("%lf %lf", &v[i].x, &v[i].y);
}
void Write()
{
printf("%d\n",vf);
for(int i = 1; i <= vf; ++i) printf("%lf %lf\n", stiva[i].x, stiva[i].y);
}
void Solve()
{
int i,pos=1;
for(i = 2; i <= N; ++i)
if( v[pos] > v[i] ) pos = i;
swap(v[1], v[pos]);
sort(v+2,v+N+1,cmp);
vf = 2;
stiva[1] = v[1];
stiva[2] = v[2];
for(i = 3; i <= N; ++i)
{
while( vf >= 2 && ceas_trig(stiva[vf-1], stiva[vf], v[i]) < 0 ) --vf;
stiva[++vf] = v[i];
}
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
Read();
Solve();
Write();
return 0;
}