Pagini recente » Cod sursa (job #2868515) | Cod sursa (job #2482670) | Istoria paginii runda/jfdf5634/clasament | template/autor-necunoscut | Cod sursa (job #509595)
Cod sursa(job #509595)
#include <iostream>
#include <fstream>
#define nmax 100005
#include <cmath>
#include <cstdio>
#include <complex>
using namespace std;
int i,n,mxp;
int sol[nmax],last,k,move,signe,stk[nmax],vf;
double mx,cosine[nmax],mxy=25000;
struct pct
{
double x, y, cs;
}P[nmax];
double ccw(int p1,int p2,int p3)
{
return (P[p2].x - P[p1].x)*(P[p3].y - P[p1].y) - (P[p2].y - P[p1].y)*(P[p3].x - P[p1].x);
}
double argume(int i)
{
double cosine;
if(P[i].x >= P[1].x)
{
double d1=P[i].x-P[1].x;
double d2=sqrt((P[i].x-P[1].x)*(P[i].x-P[1].x) + (P[i].y-P[1].y)*(P[i].y-P[1].y));
cosine=d1/d2;
}
else
{
double d1=P[1].x-P[i].x;
double d2=sqrt((P[i].x-P[1].x)*(P[i].x-P[1].x) + (P[i].y-P[1].y)*(P[i].y-P[1].y));
cosine=d1/d2;
cosine=cosine*(-1);
}
return cosine;
}
struct cmp
{
bool operator()(const pct &a,const pct &b)
{
if(a.cs>b.cs)
return 1;
return 0;
}
};
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lf %lf",&P[i].x,&P[i].y);
for(i=1;i<=n;i++)
{
if(P[i].x<mxy)
{
mxy=P[i].x;
mxp=i;
}
else
if(P[i].x==mxy)
{
if(P[i].y<P[mxp].y)
mxp=i;
}
}
for(i=2;i<=n;i++)
P[i].cs=argume(i);
swap(P[1],P[mxp]);
sort(P+2,P+n+1,cmp());
stk[1]=1;
stk[2]=2;
vf=2;
for(i=3;i<=n;i++)
{
while(ccw(stk[vf-1],stk[vf],i)<=0 && vf>=2)
vf--;
stk[++vf]=i;
}
printf("%d\n",vf);
/*for(i=1;i<=n;i++)
printf("%lf %lf\n",P[i].x, P[i].y);
printf("\n");*/
for(i=1;i<=vf;i++)
printf("%lf %lf\n",P[stk[i]].x, P[stk[i]].y);
return 0;
}