📄 usaco 3_4_1 closed fences题解_leokan的blog.mht
字号:
if cut1(u,v)=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p;  =
;=20
=
writeln('NOFENCE');<BR> &n=
bsp; &nb=
sp; =20
=
close(output);<BR> &=
nbsp; &n=
bsp; =20
=
exit;<BR> &nbs=
p; =20
=
end;<BR>  =
;=20
end;<BR> u.a:=3Dcorner[n];<BR> =
u.b:=3Dcorner[1];<BR> for j:=3D1 to n-1=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
v.a:=3Dcorner[j];<BR> &nbs=
p; =20
=
v.b:=3Dcorner[j+1];<BR> &n=
bsp; =20
if cut1(u,v)=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
writeln('NOFENCE');<BR> &n=
bsp; =20
=
close(output);<BR> &=
nbsp; =20
=
exit;<BR> &nbs=
p; =20
end;<BR> =20
end;<BR> =20
fillchar(used,sizeof(used),0);<BR> =20
count:=3D0;<BR> for i:=3D1 to n-2=20
do<BR> =20
=
begin<BR> &nbs=
p;=20
=
v.a:=3Dcorner[i];<BR> &nbs=
p; =20
=
v.b:=3Dcorner[i+1];<BR> &n=
bsp; =20
=
used[i]:=3Dtrue;<BR>  =
; =20
if see(v)=20
=
then<BR>  =
; =20
=
begin<BR> &nbs=
p; =20
=
inc(count);<BR> &nbs=
p; =20
=
ans[count]:=3Dv;<BR>  =
; =20
=
end;<BR>  =
;=20
used[i]:=3Dfalse;<BR> =20
end;<BR> v.a:=3Dcorner[1];<BR> =
v.b:=3Dcorner[n];<BR> =
used[n]:=3Dtrue;<BR> =20
if see(v) then<BR> =20
=
begin<BR> &nbs=
p;=20
=
inc(count);<BR> &nbs=
p; =20
ans[count]:=3Dv;<BR> =20
end;<BR> used[n]:=3Dfalse;<BR> =
v.a:=3Dcorner[n-1];<BR> =20
v.b:=3Dcorner[n];<BR> =20
used[n-1]:=3Dtrue;<BR> if see(v)=20
then<BR> =20
=
begin<BR> &nbs=
p;=20
=
inc(count);<BR> &nbs=
p; =20
ans[count]:=3Dv;<BR> =20
end;<BR> =
used[n-1]:=3Dfalse;<BR> =20
writeln(count);<BR> for i:=3D1 to count=20
do<BR> =
writeln(ans[i].a.x:0:0,'=20
',ans[i].a.y:0:0,' ',ans[i].b.x:0:0,'=20
',ans[i].b.y:0:0);<BR> =20
close(output);<BR>end;<BR>begin<BR> =20
init;<BR> =20
=
work;<BR>end. =
=20
<BR></STRONG></P><STRONG>
<DIV class=3Dt_msgfont>
<HR>
</DIV></STRONG>
<P class=3Dt_msgfont></P>
<P class=3Dt_msgfont></P>
<DIV class=3Dt_msgfont align=3Dcenter forimg=3D"1"></DIV>
<P class=3Dt_msgfont></P>
<P class=3Dt_msgfont align=3Dleft =
forimg=3D"1"><STRONG>USACO=B5=C4=B7=D6=CE=F6</STRONG></P>
<P class=3Dt_msgfont align=3Dleft forimg=3D"1"><STRONG>Determining =
if the fence=20
is simple is, um, simple. For each pair of segments which don't =
share a=20
vertex, determine if they intersect. If they do, the fence isn't =
simple.=20
Otherwise, it is. </STRONG></P>
<P class=3Dt_msgfont align=3Dleft forimg=3D"1"><STRONG>Let =
<EM>p</EM> be the=20
point given. Given another point <EM>q</EM> and a segment =
<EM>e</EM>,=20
using the techniques described in the computation geometry module, =
we can=20
determine the following: </STRONG></P>
<DIV class=3Dt_msgfont align=3Dleft forimg=3D"1">
<OL>
<LI><STRONG>Whether the ray <EM>pq</EM> intersects <EM>e</EM> =
</STRONG>
<LI><STRONG>If it does, how far along that ray the intersection =
takes=20
place </STRONG></LI></OL></DIV>
<P class=3Dt_msgfont align=3Dleft><STRONG>Thus, we can determine =
the first=20
segment intersected by the ray, which must be visible to the =
point. By=20
checking all points <EM>q</EM> in the plane, we could determine =
all the=20
visible faces. The problem with this is, of course, that checking =
all=20
points <EM>q</EM> is impossible. </STRONG></P>
<P class=3Dt_msgfont align=3Dleft><STRONG>Instead, check for all =
endpoints of=20
segments and all midpoints of segments. If an edge <EM>e</EM> is =
visible,=20
then either its midpoint is visible, or some set of edges obscure =
it. If=20
some set of edges obscure <EM>e</EM>, then there is some edge =
where=20
<EM>e</EM> is visible 'just beyond' one of its endpoints. In this =
case, if=20
we do our intersection test such that 'brushing' an endpoint of a =
segment=20
does not count as intersecting it, then the ray from the observer =
to that=20
endpoint will intersect the edge <EM>e</EM> first. </STRONG></P>
<P class=3Dt_msgfont align=3Dleft><STRONG>Thus, for each endpoint =
and=20
midpoints, we determine the first edge intersected, and mark it as =
visible. </STRONG></P>
<DIV class=3Dt_msgfont align=3Dleft><PRE><STRONG>/*
PROB: fence4
ID: hburch002
*/
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define SQR(A) ((A)*(A))
/* maximum number of points */
#define MAXN 201
/* number of points */
int npos;
/* the points, where pos[npos] =3D=3D pos[0] */
double pos[MAXN][2];
/* observer's location */
double obsx, obsy;
/* cansee[x] =3D can we see the segment (x,x+1)? */
int cansee[MAXN];
int side(double sx, double sy, double ex, double ey, int p)
{ /* determine the side that the points lie on */
double dx, dy;
double px, py;
double t;
dx =3D ex - sx;
dy =3D ey - sy;
px =3D pos[p][0] - sx;
py =3D pos[p][1] - sy;
/* take cross-product */
t =3D dx * py - dy * px;
if (t > 0.00001) return 0; /* "left" side */
if (t < -0.00001) return 1; /* "right" side */
return 2; /* on the line */
}
int first_inter(double sx, double sy, double ex, double ey)
{ /* what is the first segment intersected by the ray s->e */
int lv; /* loop variable */
int t1, t2;
int s1, s2;
double ax, ay, bx, by;
double t;
double coeff, cnst;
double i, j;
double x, y;
double mlbrush, mrbrush; /* when is the earliest brush on a side? */
/* min =3D distance to nearest intersection point */
/* mloc =3D edge where this occurs */
double min =3D 1e10; /* ~=3D infinity */
int mloc =3D npos; /* unused location */
mlbrush =3D mrbrush =3D 1e10; /* infinity */
for (lv =3D 0; lv < npos; lv++)
{ /* for each segment, determine length along */
ax =3D pos[lv][0];
ay =3D pos[lv][1];
bx =3D pos[lv+1][0];
by =3D pos[lv+1][1];
/* take cross product */
t =3D (ex - sx) * (ay - by) - (ey - sy) * (ax - bx);
if (t > -0.00001 && t < 0.00001) /* parallel */
continue; /* not considered visible */
/* not parallel */
/* we are now solving the following equations:
(ex - sx) j + sx =3D (bx - ax) i + ax
(ey - sy) j + sy =3D (by - ay) i + ay
*/
/* solves for alpha by multiple first by (by - ay) and
the second by (bx - ax) and subtracting equations */
cnst =3D (ax - sx)*(by - ay) - (ay - sy)*(bx - ax);
coeff =3D (ex - sx) * (by - ay) - (ey - sy) * (bx - ax);
if (coeff > -0.00001 && coeff < .00001)
{ /* degenerate, one of bx - ax and by - ay is about zero */
if (bx - ax > -.00001 && bx - ax < 0.00001)
{ /* bx - ax =3D=3D 0, can solve first eqn directly */
cnst =3D ax - sx;
coeff =3D ex - sx;
} else { /* by - ay =3D=3D 0, can solve second eqn directly */
cnst =3D ay - sy;
coeff =3D ey - sy;
}
}
j =3D cnst / coeff;
/* if intersection occurs before starting point, no intersection */
if (j < -.00001) continue;
/* determine beta */
cnst =3D sx + (ex - sx) * j - ax;
coeff =3D bx - ax;
if (coeff > -0.00001 && coeff < .00001)
{ /* handle degeneracy */
cnst =3D sy + (ey - sy) * j - ay;
coeff =3D by - ay;
}
i =3D cnst / coeff;
/* if the interesection occurs with i < 0 | i > 1, the
intersection is not within the confines of the segment */
if (i < -.00001 || i > 1.00001) continue;
/* calculate intersection point */
x =3D ax + (bx - ax) * i;
y =3D ay + (by - ay) * i;
/* determine distance along line that intersection occurs */
t =3D (x - sx) * (ex - sx) + (y - sy) * (ey - sy);
/* make sure it's in bounds, and better than what we have */
if (t < -0.00001 || t > min) continue;
=20
/* if it occurs at an end point */
if (i < .00001 || i > 0.99999)=20
{
/* find the endpoints that are incident to the intersected =
endpoint */
if (i < .00001)
{
t1 =3D lv-1;
if (t1 < 0) t1 +=3D npos;
t2 =3D lv+1;
} else {
t1 =3D lv;
t2 =3D lv+2;
if (t2 >=3D npos) t2 -=3D npos;
}
/* if they lie on the same side of the line, then ray 'brushes'
endpoint, which is not considered to an intersection */
s1 =3D side(sx,sy,ex,ey,t1);
s2 =3D side(sx,sy,ex,ey,t2);
if (s1 =3D=3D s2) {
if (s1 =3D=3D 0 && t < mlbrush) mlbrush =3D t;
if (s1 =3D=3D 1 && t < mrbrush) mrbrush =3D t;
continue;
}
}
/* found a better edge! */
min =3D t;
mloc =3D lv;
}
/* if it brushes on both sides, it cannot be seen */
if (min > mlbrush && min > mrbrush) return npos;
return mloc;
}
int check_intersect(int f1, int f2)=20
{ /* do (f1,f1+1) and (f2,f2+1) intersect? */
double sx, sy;
double ex, ey;
=20
sx =3D pos[f1][0];
sy =3D pos[f1][1];
ex =3D pos[f1+1][0];
ey =3D pos[f1+1][1];
if (side(sx, sy, ex, ey, f2) =3D=3D side(sx, sy, ex, ey, f2+1))
/* are the f2 and f2+1 on the same side of (f1,f1+1)? */
return 0; /* if so, the segments don't intersect */
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -