Pagini recente » Cod sursa (job #2335746) | Cod sursa (job #2230495) | Cod sursa (job #1185812) | Cod sursa (job #2702575) | Cod sursa (job #583965)
Cod sursa(job #583965)
#include<stdio.h>
#include<algorithm>
#define Nmax 120001
#define INF 1000000010
using namespace std;
int N,minP,st[Nmax];
struct pct
{
double x,y;
}v[Nmax],p,var;
void read()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&N);
int i;
p.x = p.y = INF;
for(i=1;i<=N;++i)
{
scanf("%lf%lf",&v[i].x,&v[i].y);
if(v[i].x<p.x || v[i].x==p.x && v[i].y<p.y)
{
p = v[i];
minP = i;
}
}
}
int cmpf(pct a,pct b)
{
return ( (a.x-p.x)*(b.y-p.y) ) > ( (a.y-p.y)*(b.x-p.x) );
}
double det(double x1,double y1,double z1,double x2,double y2,double z2,double x3,double y3,double z3)
{
return (x1*y2*z3 + x2*y3*z1 + x3*y1*z2 - z1*y2*x3 - z2*y3*x1 - z3*y1*x2);
}
int main()
{
read();
int i;
var = v[minP];
v[minP] = v[1];
v[1] = var;
sort(v+2,v+N+1,cmpf);
st[1] = 1;
st[2] = 2;
int lev = 2;
for(i=3;i<=N;++i)
{
while(lev>=2 && det(v[st[lev-1]].x, v[st[lev-1]].y, 1.0f, v[st[lev]].x, v[st[lev]].y, 1.0f,v[i].x, v[i].y, 1.0f) < 0)
--lev;
st[++lev] = i;
}
printf("%d\n",lev);
for(i=1;i<=lev;++i)
printf("%lf %lf\n",v[st[i]].x,v[st[i]].y);
return 0;
}