Pagini recente » Cod sursa (job #1141612) | Cod sursa (job #148649) | Cod sursa (job #2935926) | Cod sursa (job #2731553) | Cod sursa (job #2756367)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX=120000;
const double eps=1e-14;
struct POINT
{
int x,y;
};
POINT P[NMAX+5],LL;
int h[NMAX+5];
double cp(POINT&a, POINT&b, POINT&c)
{
return 1.0*(b.x-a.x)*(c.y-b.y)-1.0*(b.y-a.y)*(c.x-b.x);
}
int ccw(POINT&a, POINT&b, POINT&c)
{
if(fabs(cp(a,b,c))<eps)
return 0;
if(cp(a,b,c)>eps)
return 1;
return -1;
}
bool cmp(POINT&a,POINT&b)
{
return ccw(LL,a,b)>0;
}
int main()
{
int n,i,top;
double x,y;
fin>>n>>x>>y;
P[0].x=x;
P[0].y=y;
for(i=1;i<n;i++)
{
fin>>x>>y;
P[i].x=x;
P[i].y=y;
if(fabs(y-P[0].y)<eps)
{
if(x-P[0].x<=-eps)
swap(P[0],P[i]);
}
else if(y-P[0].y<=-eps)
swap(P[i],P[0]);
}
LL=P[0];
sort(P+1,P+n,cmp);
P[n]=P[0];
h[0]=0;
h[1]=1;
top=1;
i=2;
/*for(i=0;i<n;i++)
{
fout<<P[i].x<<' '<<P[i].y<<'\n';
}*/
while(i<=n)
{
if(ccw(P[h[top-1]],P[h[top]],P[i])>0)
{
h[++top]=i;
i++;
}
else
top--;
}
fout<<top<<'\n';
for(i=0;i<top;i++)
{
fout<<fixed<<setprecision(6)<<P[h[i]].x<<' '<<P[h[i]].y<<'\n';
}
return 0;
}