Pagini recente » Cod sursa (job #1647351) | Cod sursa (job #1166778) | Cod sursa (job #1431195) | Cod sursa (job #2835791) | Cod sursa (job #2756502)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const double eps=1.0e-14;
const double INF=1e9;
const int NMAX=120000;
struct POINT
{
double x,y;
}P[NMAX+5],LL;
int h[NMAX+5];
double cp(const POINT &P1,const POINT &P2,const POINT &P3)
{
return (P2.x-P1.x)*(P3.y-P2.y)-(P2.y-P1.y)*(P3.x-P2.x);
}
int ccw(const POINT &P1,const POINT &P2,const POINT &P3)
{
double crossp=cp(P1,P2,P3);
if(fabs(crossp)<eps)return 0;
if(crossp>=eps)return 1;
return -1;
}
bool cmp(POINT P1,POINT P2)
{
return ccw(LL,P1,P2)>0;
}
double arie_poligon(int n)
{
double aria=0;
P[n]=P[0];
for(int i=0;i<n;i++)
aria+=P[i].x*P[i+1].y-P[i+1].x*P[i].y;
aria=0.5*fabs(aria);
return aria;
}
int main()
{
int n,i;
double a,b;
cin>>n>>a>>b;
P[0].x=a;
P[0].y=b;
for(i=1;i<=n;i++)
{
cin>>a>>b;
P[i].x=a;
P[i].y=b;
if((P[i].y-P[0].y<=-eps)||(fabs(P[i].y-P[0].y<eps)&&(P[i].x-P[0].x<=-eps)))
swap(P[0],P[i]);
}
LL=P[0];
sort(P+1,P+n,cmp);
P[n]=P[0];
h[0]=0;
h[1]=1;
int top=1;
i=2;
while(i<=n)
{
if(ccw(P[h[top-1]],P[h[top]],P[i])>0)
{
h[++top]=i;
i++;
}
else top--;
}
cout<<top<<'\n';
for(int i=0;i<top;i++)
cout<<fixed<<setprecision(6)<<P[h[i]].x<<" "<<P[h[i]].y<<'\n';
return 0;
}