Pagini recente » Cod sursa (job #2414684) | Cod sursa (job #1018477) | Cod sursa (job #1818683) | Cod sursa (job #307421) | Cod sursa (job #1850870)
#include<fstream>
#include<iomanip>
#include<vector>
#include<algorithm>
#define dim 120005
#define eps 1e-12
using namespace std;
struct punct
{
double x,y;
};
punct v[dim];
bool in[dim];
int s[dim],n,h;
void citire()
{
ifstream fin("infasuratoare.in");
fin>>n;
for(int i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
fin.close();
}
int cmp(double a, double b)
{
if(a+eps<b)
return 1;
if(b+eps<a)
return -1;
return 0;
}
bool cmpXY(punct a, punct b)
{
int rez=cmp(a.x,b.x);
if(rez!=0)
return (rez==1);
return cmp(a.y,b.y)==1;
}
int semn(punct a, punct b, punct c)
{
double arie=a.x*(b.y-c.y)-a.y*(b.x-c.x)+b.x*c.y-b.y*c.x;
return cmp(arie,0);
}
void graham()
{
int varf, alt,i;
sort(v+1,v+n+1,cmpXY);
s[1]=1;s[2]=2;
in[2]=1;
i=3;
varf=2;
alt=1;
while(in[1]==0)
{
while(in[i]!=0)
{
if(i==n)
alt=-1;
i+=alt;
}
while(varf>=2 && semn(v[s[varf-1]], v[s[varf]], v[i])==-1)
{
in[s[varf]]=0;
varf--;
}
s[++varf]=i;
in[i]=1;
}
h=varf-1;
}
int main()
{
ofstream fout("infasuratoare.out");
citire();
graham();
fout<<fixed<<h<<"\n";
for(int i=h+1;i>=2;i--)
fout<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";
return 0;
}