Pagini recente » Cod sursa (job #3267741) | Cod sursa (job #3285062) | Cod sursa (job #2917278) | Cod sursa (job #1081060) | Cod sursa (job #932497)
Cod sursa(job #932497)
#include <cstdio>
#include <algorithm>
using namespace std;
FILE *f=fopen("infasuratoare.in","r");
FILE *g=fopen("infasuratoare.out","w");
#define eps 1e-12
#define Nmax 120001
int n,i,h,k;
struct punct {
double x,y;
}p[Nmax],v[Nmax],minx;
int s[Nmax],ok[Nmax];
inline int cmp1(double a,double b) {
if (a+eps<b) return 1;
if (b+eps<a) return -1;
return 0;
}
bool cmp(const punct &a,const punct &b)
{
int t;
t=cmp1(a.x,b.x);
if (t!=0) return t==1;
return (cmp1(a.y,b.y)==1);
}
int semn(punct a,punct b,punct c)
{
return cmp1((a.y-b.y)*c.x+(b.x-a.x)*c.y+a.x*b.y - b.x*a.y,0);
}
void rezolva()
{
int k,q;
sort(v+1,v+n+1,cmp);
s[1]=1; s[2]=2;
ok[2]=1;
k=2;
i=3;
q=1;
while (!ok[1])
{
while (ok[i])
{
if (i==n) q=-1;
i+=q;
}
while (k>=2 && semn(v[s[k-1]],v[s[k]],v[i])==-1)
{
ok[s[k--]]=0;
}
s[++k]=i;
ok[i]=1;
}
h=k-1;
}
int main ()
{
fscanf(f,"%d",&n);
for (i=1; i<=n; i++)
fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
rezolva();
fprintf(g,"%d\n",h);
for(i=h+1;i>=2;i--)
fprintf(g,"%lf %lf\n",v[s[i]].x,v[s[i]].y);
fclose(f);
fclose(g);
return 0;
}