Pagini recente » Cod sursa (job #429737) | Cod sursa (job #2796708) | Cod sursa (job #664847) | Cod sursa (job #29679) | Cod sursa (job #753875)
Cod sursa(job #753875)
#include<stdio.h>
#include<algorithm>
#include<math.h>
#define eps 1.e-12
using namespace std;
struct casy
{
double x,y;
void operator = (const casy &other) {
x=other.x;
y=other.y;
}
};
casy p[120005];
casy ll;
int sol[120005];
int nrsol;
bool cmp(casy p1,casy p2)
{
double ccw,d1,d2;
ccw=(p1.x-ll.x)*(p2.y-p1.y)-(p1.y-ll.y)*(p2.x-p1.x);
if(ccw>eps)
return 1;
if(fabs(ccw)<eps) {
d1=(p1.x-ll.x)*(p1.x-ll.x)+(p1.y-ll.y)*(p1.y-ll.y);
d2=(p2.x-ll.x)*(p2.x-ll.x)+(p2.y-ll.y)*(p2.y-ll.y);
if(d2-d1>eps)
return 1;
}
return 0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n,i,poz;
casy aux;
double ccw;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
ll.x=p[1].x;
ll.y=p[1].y;
poz=i;
for(i=2;i<=n;i++)
{
if(fabs(ll.y-p[i].y)<eps&&ll.x-p[i].x>eps) {
ll.x=p[i].x;
ll.y=p[i].y;
poz=i;
}
if(ll.y-p[i].y>eps)
{
poz=i;
ll.x=p[i].x;
ll.y=p[i].y;
}
}
aux=p[poz];
p[poz]=p[1];
p[1]=aux;
sort(p+2,p+n+1,cmp);
sol[1]=1;
sol[2]=2;
nrsol=2;
p[n+1].x=p[1].x;
p[n+1].y=p[1].y;
for(i=3;i<=n+1;i++)
{
ccw=(p[sol[nrsol]].x-p[sol[nrsol-1]].x)*(p[i].y-p[sol[nrsol]].y)-(p[sol[nrsol]].y-p[sol[nrsol-1]].y)*(p[i].x-p[sol[nrsol]].x);
if(ccw>eps)
sol[++nrsol]=i;
else
{
nrsol--;
i--;
}
}
printf("%d\n",nrsol-1);
for(i=1;i<nrsol;i++)
printf("%lf %lf\n",p[sol[i]].x,p[sol[i]].y);
return 0;
}