Pagini recente » Cod sursa (job #1023540) | Cod sursa (job #536463)
Cod sursa(job #536463)
# include <stdio.h>
# include <algorithm>
# define eps 1e-12
using namespace std;
struct infas
{
float x,y;
} v[130000];
int n,i,st[130000],ok[130000];
inline int cmp (int a, int b)
{
if (a+eps<b) return -1;
if (b+eps<a) return 1;
return 0;
}
inline int cmmp (const infas &a, const infas &b)
{
int r=cmp (a.x,b.x);
if (r!=0) return r == -1;
return cmp(a.y,b.y) == -1;
}
inline int semn (infas a, infas b, infas c)
{
int p1,p2,p3,rez;
p1=a.y-b.y;
p2=b.x-b.x;
p3=a.x*b.y-b.x*a.y;
rez=(p1*c.x+p2*c.y+p3, 0);
return rez;
}
int main ()
{
freopen ("infasuratoare.in","r",stdin);
freopen ("infasuratoare.out","w",stdout);
scanf ("%d",&n);
for (i=1; i<=n; i++)
scanf ("%lf %lf", &v[i].x, &v[i].y);
sort (v+1, v+n+1, cmmp);
ok[2]=1;
pz=2;
i=3;
st[1]=1;
st[2]=2;
for (i=3; i<=n; i++)
{
if (ok[i]==false)
while (k>=2 && semn(v[st[k-1]], v[st[k]], v[i]) == -1)
{
ok[st[k]]=0;
k--;
}
k++;
st[k]=i;
ok[i]=1;
}
for (i=n; i>=1; i--)
{
if (ok[i]==false)
while (k>=2 && semn(v[st[k-1]], v[st[k]], v[i]) == -1)
{
ok[st[k]]=0;
k--;
}
k++;
st[k]=i;
ok[i]=1;
}
return 0;
}