Pagini recente » Cod sursa (job #347361) | Cod sursa (job #761082) | Cod sursa (job #2498761) | Cod sursa (job #1363773) | Cod sursa (job #538160)
Cod sursa(job #538160)
#include <stdio.h>
#include <algorithm>
#define N 120001
using namespace std;
typedef struct {float x,y;} PUNCT;
PUNCT X[N];
PUNCT S[N];
int n,i,s;
FILE *f,*g;
bool operator < (const PUNCT &a, const PUNCT &b)
{
if (a.y<b.y)
return 1;
else if (a.y==b.y)
if (a.x<b.x)
return 1;
return 0;
}
int stanga(PUNCT &a, PUNCT &b, PUNCT &c)
{
float st;
st=a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-a.y*b.x-c.y*a.x;
if (st>0)
return 1;
else return 0;
}
int main()
{
f=fopen("infasuratoare.in","r");
g=fopen("infasuratoare.out","w");
fscanf(f,"%d",&n);
for (i=1;i<=n;++i)
fscanf(f,"%f %f",&X[i].x,&X[i].y);
sort(X+1,X+n+1);
s=2;
S[1]=X[1];
S[2]=X[2];
i=3;
while (i<=n)
{
if (stanga(S[s-1],S[s],X[i]))
{
S[++s]=X[i];
++i;
}
else
{
s--;
if (s<2)
{
S[++s]=X[i];
++i;
}
}
}
i=n-1;
while (i>1)
{
if (stanga(S[s-1],S[s],X[i]))
{
S[++s]=X[i];
i--;
}
else if (X[i].x!=S[s].x || X[i].y!=S[s].y)
{
if (X[i].x!=S[s-1].x || X[i].x!=S[s-1].y)
s--;
else i--;
}
else i--;
}
fprintf(g,"%d\n",s);
for (i=1;i<=s;++i)
fprintf(g,"%f %f\n",S[i].x,S[i].y);
fclose(f);
fclose(g);
return 0;
}