Pagini recente » Cod sursa (job #2616311) | Cod sursa (job #1107177) | Cod sursa (job #140762) | Cod sursa (job #1341542) | Cod sursa (job #309187)
Cod sursa(job #309187)
#include <fstream>
#include <iomanip>
#include <math.h>
#define dim 120010
using namespace std;
ifstream f("infas.in");
ofstream g("infas.out");
int n,k;
typedef struct
{
double x,y,u1,u2;
} Punct;
Punct p[dim],pv,s[dim];
void swap(Punct &p1,Punct &p2)
{
Punct px=p1;
p1=p2;
p2=px;
}
void read()//citeste punctele si stabileste pivotul
{
int i,j;
f>>n;
for(i=1;i<=n;i++)
{
f>>p[i].x>>p[i].y;
if(i==1)
{
pv=p[i];
j=i;
}
else if(p[i].y-pv.y<0)
{
pv=p[i];
j=i;
}
else if(p[i].y-pv.y==0&&p[i].x-pv.x<0)
{
pv=p[i];
j=i;
}
}
swap(p[j],p[1]);//plaseaza pivotul pe prima pozitie
}
void assign()
{
int i;
for(i=2;i<=n;i++)
{
p[i].u1=(p[i].y-p[1].y);
p[i].u2=(p[i].x-p[1].x);
}
}
void quicks(int l,int r)
{
int i,j;
j=l-1;
for(i=l;i<=r;i++)
{
if((p[i].u1*p[r].u2)<=(p[r].u1*p[i].u2))
swap(p[i],p[++j]);
}
if(l<j-1)
quicks(l,j-1);
if(r>j+1)
quicks(j+1,r);
}
double clock(Punct p1,Punct p2,Punct p3)
{
return (p3.x-p1.x)*(p2.y-p1.y)-(p3.y-p1.y)*(p2.x-p1.x);
}
void graham()
{
assign();
quicks(2,n);
p[n+1]=s[++k]=p[1];
int i;
for(i=2;i<=n;i++)
{
if(clock(s[k],p[i],p[i+1])<0)
s[++k]=p[i];
}
}
void write()
{
g<<k<<endl;
for(int i=1;i<=k;i++)
{
g<<setprecision(6)<<s[i].x;
g<<" ";
g<<setprecision(6)<<s[i].y<<endl;
}
/* g<<setprecision(6)<<s[i].x;
g<<" ";
g<<setprecision(6)<<s[i].y<<endl;
*/
}
int main()
{
read();
graham();
write();
return 0;
}