Pagini recente » Cod sursa (job #3162860) | Cod sursa (job #698430) | Cod sursa (job #1713368) | Cod sursa (job #863382) | Cod sursa (job #2332478)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
const int NMAX=120005;
const double eps=1e-14;
struct POINT
{
double x,y;
};
POINT v[NMAX],LL;
int h[NMAX];
double cp(POINT P1,POINT P2,POINT P3)
{
return (P2.x-P1.x)*(P3.y-P2.y)-(P2.y-P1.y)*(P3.x-P2.x);
}
int ccw(POINT P1,POINT P2,POINT P3)
{
double c=cp(P1,P2,P3);
if(fabs(c)<eps)
return 0;
if(c>=eps)
return 1;
return -1;
}
bool cmp(POINT P1,POINT P2)
{
int sccw=ccw(LL,P1,P2);
if(sccw>0)
return 1;
return 0;
}
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int main()
{
int n,i,top;
POINT temp;
double X,Y;
in>>n>>X>>Y;
temp.x=X;
temp.y=Y;
v[0]=temp;
for(i=1;i<n;i++)
{
in>>X>>Y;
v[i].x=X;
v[i].y=Y;
if(((Y-v[0].y)<=-eps)||(fabs(Y-v[0].y)<eps&&(X-v[0].x)<=-eps))
swap(v[0],v[i]);
}
LL=v[0];
sort(v+1,v+n,cmp);
v[n]=LL;
h[1]=0;
h[2]=1;
top=2;
i=2;
while(i<=n)
{
if(ccw(v[h[top-1]],v[h[top]],v[i])>0)
{
h[++top]=i;
i++;
}
else
top--;
}
out<<top-1<<"\n";
out<<fixed<<showpoint<<setprecision(6);
for(i=1;i<top;i++)
out<<v[h[i]].x<<" "<<v[h[i]].y<<"\n";
return 0;
}