usaco 3_4_1 closed fences题解_leokan的blog.mht

美国USACO题库源程序

  sx =3D pos[f2][0];
  sy =3D pos[f2][1];
  ex =3D pos[f2+1][0];
  ey =3D pos[f2+1][1];

  if (side(sx, sy, ex, ey, f1) =3D=3D side(sx, sy, ex, ey, f1+1))
  /* are f1 & f1+1 on the same side of (f2,f2+1) */
    return 0; /* if so, the segments don't intersect */

  /* the endpoints of each segment are on opposite sides of
     the other segment.  Therefore, they intersect */
  return 1;=20
 }

int main(int argc, char **argv)
 {
  FILE *fout, *fin;
  int lv, lv2;
  int cnt;
  int t;
  double dx, dy;

  if ((fin =3D fopen("fence4.in", "r")) =3D=3D NULL)
   {
    perror ("fopen fin");
    exit(1);
   }
  if ((fout =3D fopen("fence4.out", "w")) =3D=3D NULL)
   {
    perror ("fopen fout");
    exit(1);
   }

  fscanf (fin, "%d", &npos);
  fscanf (fin, "%lf %lf", &obsx, &obsy);
  for (lv =3D 0; lv < npos; lv++)
    fscanf (fin, "%lf %lf", &pos[lv][0], &pos[lv][1]);
  pos[npos][0] =3D pos[0][0];
  pos[npos][1] =3D pos[0][1];

/* for each pair of segments that don't share a vertex */
  for (lv =3D 0; lv < npos; lv++)
    for (lv2 =3D lv+2; lv2 < npos; lv2++)
      if (check_intersect(lv, lv2))
       { /* if they intersect */

        /* and don't share a vertex */
        if (lv =3D=3D 0 && lv2 =3D=3D npos-1) continue;=20

        /* then the fence is invalid */
        fprintf (fout, "NOFENCE\n");=20
        return 0;
       }

  for (lv =3D 0; lv < npos; lv++)
   {
    /* check endpoint */
    cansee[first_inter(obsx, obsy, pos[lv][0], pos[lv][1])] =3D 1;

    /* check midpoint of segment (lv, lv+1) */
    cansee[first_inter(obsx, obsy,=20
               (pos[lv][0] + pos[lv+1][0])*0.5,=20
               (pos[lv][1] + pos[lv+1][1])*0.5)] =3D 1;
   }

  /* count number of visible segments */
  cnt =3D 0;
  for (lv =3D 0; lv < npos; lv++)
    if (cansee[lv]) cnt++;

  fprintf (fout, "%i\n", cnt);

  /* list visible segments */
  for (lv =3D 0; lv < npos-2; lv++)
    if (cansee[lv])
     {
      fprintf (fout, "%.0f %.0f %.0f %.0f\n", pos[lv][0], pos[lv][1],=20
            pos[lv+1][0], pos[lv+1][1]);
     }
  /* because of the way the ordering is defined, these two must be
     checked separately */
  if (cansee[npos-1])
   {
    fprintf (fout, "%.0f %.0f %.0f %.0f\n", pos[0][0], pos[0][1],=20
          pos[npos-1][0], pos[npos-1][1]);
   }
  if (cansee[npos-2])
   {
      fprintf (fout, "%.0f %.0f %.0f %.0f\n", pos[npos-2][0], =
pos[npos-2][1],=20
            pos[npos-2+1][0], pos[npos-2+1][1]);
   }
  =20
  return 0;
 }</STRONG></PRE></DIV></DIV></TD></TR></TBODY></TABLE><BR>
<DIV class=3Dopt><A =
title=3D=B2=E9=BF=B4=B8=C3=B7=D6=C0=E0=D6=D0=CB=F9=D3=D0=CE=C4=D5=C2=20
href=3D"http://hi.baidu.com/leokan/blog/category/Oi">=C0=E0=B1=F0=A3=BAOi=
</A> | <A=20
title=3D=BD=AB=B4=CB=CE=C4=D5=C2=CC=ED=BC=D3=B5=BD=B0=D9=B6=C8=CB=D1=B2=D8=
 onclick=3D"return addToFavor();"=20
href=3D"http://cang.baidu.com/do/add" =
target=3D_blank>=CC=ED=BC=D3=B5=BD=CB=D1=B2=D8</A> | =E4=AF=C0=C0(<SPAN=20
id=3Dresult></SPAN>) | <A=20
href=3D"http://hi.baidu.com/leokan/blog/item/99577bc6a7834e1f9c163d4c.htm=
l#send">=C6=C0=C2=DB</A>&nbsp;(2)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D =
[true,'=D2=BB=C6=F0=C8=A5=C7=EB=D4=B8=CD=F8=D5=BE=C7=A9=C3=FB=D7=E8=D6=B9=
=BA=AB=B9=FA=C2=D3=B6=E1=D6=D0=B9=FA=CE=C4=BB=AF=D2=C5=B2=FA!', =
'=D2=BB=C6=F0=C8=A5=C7=EB=D4=B8=CD=F8=D5=BE=C7=A9=C3=FB=D7=E8=D6=B9=BA=AB=
=B9=FA=C2=D3=B6=E1...','/leokan/blog/item/7b334a10f999b4f8c2ce7923.html']=
;
var post =3D [true,'USACO 3.4.2 American Heritage =CC=E2=BD=E2','USACO =
3.4.2 American Heritage ...', =
'/leokan/blog/item/d9ae0424f93b162fd40742bb.html'];
if(pre[0] || post[0]){
	document.write('<div =
style=3D"height:5px;line-height:5px;">&nbsp;</div><div id=3D"in_nav">');
	if(pre[0]){
		document.write('=C9=CF=D2=BB=C6=AA=A3=BA<a href=3D"' + pre[3] + '" =
title=3D"' + pre[1] + '">' +  pre[2] + '</a>&nbsp;&nbsp;&nbsp;&nbsp;');
	}
	if(post[0]){
		document.write('=CF=C2=D2=BB=C6=AA=A3=BA<a href=3D"' + post[3] + '" =
title=3D"' + post[1] + '">' +  post[2] + '</a>');
	}
	document.write('</div>');
}
/*]]>*/
</SCRIPT>
 </DIV>
<DIV class=3Dline></DIV>
<STYLE type=3Dtext/css>#in_related_doc A {
	TEXT-DECORATION: none
}
</STYLE>

<DIV id=3Din_related_tmp></DIV>
<SCRIPT language=3Djavascript type=3Dtext/javascript>
/*<![CDATA[*/
function HI_MOD_IN_RELATED_DOC_CALLBACK(arg){
    if(arg.length <=3D 1) return false;
    var hasMore =3D arg[0];
    var D=3Dfunction(A,B){A[A.length]=3DB;}
    if(arg.length % 2 =3D=3D 0) D(arg, ["","","",""]);

    var html =3D ['<div id=3D"in_related_doc"><div =
class=3D"tit">=CF=E0=B9=D8=CE=C4=D5=C2=A3=BA</div>'];
    D(html, '<table cellpadding=3D"0" cellspacing=3D"3" border=3D"0">');
    for(var i =3D 1, j =3D arg.length; i < j; i +=3D 2){
        D(html, '<tr>');
        D(html, '<td width=3D"15px"><a style=3D"font-size:25px" =
>&#8226;</a></td><td><a href=3D"http://hi.baidu.com/' + arg[i][3] + =
'/blog/item/' + arg[i][2] + '.html" target=3D"_blank" title=3D"' + =
arg[i][0] + '">' + arg[i][1] + '</a>');
        D(html, new Array(10).join('\u3000'));
        D(html, '</td>');
        if(arg[i + 1][0] !=3D "")
            D(html, '<td width=3D"15px"><a style=3D"font-size:25px" =
>&#8226;</a></td><td><a href=3D"http://hi.baidu.com/' + arg[i + 1][3] + =
'/blog/item/' + arg[i + 1][2] + '.html" target=3D"_blank" title=3D"' + =
arg[i + 1][0] + '">' + arg[i + 1][1] + '</a></td>');
        else
            D(html, '<td>&nbsp;</td><td>&nbsp;</td>');
        D(html, '</tr>');
    }
    if(hasMore) D(html, '<tr><td colspan=3D"4"><a target=3D"_blank" =
href=3D"/sys/search?pageno=3D1&type=3D7&sort=3D1&word=3DUSACO%203%2E4%2E1=
%20Closed%20Fences%CC%E2%BD%E2&item=3D99577bc6a7834e1f9c163d4c">=B8=FC=B6=
=E0&gt;&gt;</a></td></tr>');
    D(html, '</table></div><div class=3D"line">&nbsp;</div>');

    var div =3D document.getElementById('in_related_tmp');
    if(div){
        div.innerHTML =3D html.join('');
        while(div.firstChild){
            div.parentNode.insertBefore(div.firstChild, div);
        }
        div.parentNode.removeChild(div);
    }
}

if(RelatedDocData =3D=3D -1){	// not supported xhr
    var script =3D document.createElement('script');
    script.type =3D 'text/javascript';
    script.src =3D =
'/sys/search?type=3D8&word=3DUSACO%203%2E4%2E1%20Closed%20Fences%CC%E2%BD=
%E2&item=3D99577bc6a7834e1f9c163d4c&t=3D' + new Date().getTime();
    document.getElementsByTagName('HEAD')[0].appendChild(script);
}else if(RelatedDocData =3D=3D null){
	GetAndEval =3D true;
}else{
	eval(RelatedDocData);
}

/*]]>*/
</SCRIPT>

<DIV id=3Din_reader>
<DIV class=3Dtit>=D7=EE=BD=FC=B6=C1=D5=DF=A3=BA</DIV>
<SCRIPT>

	var g_spAnnony=3Dtrue;


var g_read=3D[
=09
["yuye%5Fabc","9005797579655f6162633900","yuye_abc"],

{}
];
g_read.length=3Dg_read.length-1;

var _rh1=3D"";
var _rh2=3D"";

function wrreader(){
	_rh1 +=3D '<table width=3D"100%" ><tr>';
	_rh2+=3D'<tr>';
	if(g_spAnnony){
		_rh1+=3D'<td align=3D"center" width=3D"10%" ><img border=3D"0" =
width=3D"55" height=3D"55" =
src=3D"http://img.baidu.com/hi/img/portraitn.jpg"></td>';
		_rh2+=3D'<td>&nbsp;</td>';
		if(g_read.length>0){
			_rh1+=3D'<td align=3D"left" width=3D"12%">';
		}else{
			_rh1+=3D'<td align=3D"left" width=3D"100%">';
		}
		_rh1+=3D"<a =
href=3D'http://passport.baidu.com/?login&tpl=3Dsp&tpl_reg=3Dsp&u=3D"+myre=
f+"' =
target=3D'_self'>=B5=C7=C2=BC</a>=BA=F3=A3=AC=C4=FA=BE=CD=B3=F6=CF=D6=D4=DA=
=D5=E2=C0=EF=A1=A3</td>";
		_rh2+=3D'<td>&nbsp;</td>'
	}
	if(g_read.length=3D=3D0){
		if(!g_spAnnony){
			_rh1+=3D'<td align=3Dleft =
width=3D"100%">=D7=EE=BD=FC=BB=B9=C3=BB=D3=D0=B5=C7=C2=BC=D3=C3=BB=A7=BF=B4=
=B9=FD=D5=E2=C6=AA=CE=C4=D5=C2=A1=AD=A1=AD</td>';
			_rh2+=3D'<td>&nbsp;</td>';
		}
	}else{
		for(i=3D0,len=3Dg_read.length;i<len;i++){
			_rh1+=3D'<td align=3D"center" valign=3D"bottom" width=3D"10%" =
class=3D"user"><a href=3D"/'+g_read[i][0]+'" target=3D"_blank"><img =
border=3D"0" =
src=3D"http://himg.baidu.com/sys/portraitn/item/'+g_read[i][1]+'.jpg"></a=
></td>';
			_rh2+=3D'<td align=3D"center" valign=3D"top" class=3D"user"><a =
href=3D"/'+g_read[i][0]+'" target=3D"_blank">'+g_read[i][2]+'</a></td>';
		}
	}
	_rh1+=3D'<td width=3D"100%"></td></tr>';
	_rh2+=3D'<td></td></tr></table>';
	document.write(_rh1+_rh2);
}

wrreader();
</SCRIPT>
</DIV>
<DIV class=3Dline></DIV>
<SCRIPT language=3DJavaScript>
allkey=3Dallkey+"142d077b0bb076f40bd18714_99577bc6a7834e1f9c163d4c_";
</SCRIPT>

<DIV id=3Din_comment><A name=3Dcomment></A>
<DIV class=3Dtit>=CD=F8=D3=D1=C6=C0=C2=DB=A3=BA</DIV>
<SCRIPT>
function writecmt(type,id,cmtname,cmturl,portraitId){
	var html1=3D"";

	if(type=3D=3D1){
			html1=3D"<a name=3D'"+id+"' href=3D'"+cmturl+"' target=3D'_blank' =
title=3D'"+cmturl+"'><img  border=3D'0' =
src=3D'http://himg.baidu.com/sys/portraitn/item/"+portraitId+".jpg'><br>"=
+cmtname+"</a>";
	}else{
		if(cmtname=3D=3D"" || cmtname=3D=3D"=C4=E4=C3=FB=CD=F8=D3=D1"){
			if(cmturl=3D=3D""){
				html1=3D"<a name=3D'"+id+"'>=C4=E4=C3=FB=CD=F8=D3=D1</a>";
			}else{
				html1=3D"<a name=3D'"+id+"' href=3D'"+cmturl+"' target=3D'_blank' =
title=3D'"+cmturl+"'>"+cmtname+"</a>";
			}
		}else{
			if(cmturl=3D=3D""){
				html1=3D"<div class=3D'f14' style=3D'display:inline'>=CD=F8=D3=D1:<a =
name=3D'"+id+"'>"+cmtname+"</a></div>";
			}else{
				html1=3D"<div class=3D'f14' style=3D'display:inline'>=CD=F8=D3=D1:<a =
name=3D'"+id+"' href=3D'"+cmturl+"' target=3D'_blank' =
title=3D'"+cmturl+"'>"+cmtname+"</a></div>";
			}
		}
	}
	document.write(html1);
}

</SCRIPT>

<TABLE class=3Ditem=20
style=3D"TABLE-LAYOUT: fixed; OVERFLOW: hidden; WORD-WRAP: break-word"=20
cellSpacing=3D0 cellPadding=3D0 width=3D"100%" border=3D0 ;>
  <TBODY>
  <TR>
    <TD class=3Dindex vAlign=3Dtop width=3D"5%">1</TD>
    <TD vAlign=3Dtop align=3Dmiddle width=3D"10%">
      <DIV class=3Duser style=3D"OVERFLOW: hidden">
      <SCRIPT>
writecmt(1,"d4ec5b4e1ecbdd0cb2de0534","yuye_abc","http://hi.baidu.com/yuy=
e_abc","9005797579655f6162633900");
</SCRIPT>
      </DIV></TD>
    <TD class=3Dcnt style=3D"PADDING-LEFT: 20px"><SPAN =
class=3Ddate>2008=C4=EA02=D4=C213=C8=D5 =D0=C7=C6=DA=C8=FD=20
      13:56 </SPAN>
      <DIV class=3Ddesc=20
      style=3D"OVERFLOW: hidden; WORD-BREAK: =
normal">=BA=C3=B7=BD=B7=A8=A3=A1<BR>=CE=D2=D5=E2=B8=F6=CC=E2=CA=C7cheat=B9=
=FD=B5=C3=A1=A3</DIV></TD></TR></TBODY></TABLE>
<DIV class=3Dline></DIV>
<TABLE class=3Ditem=20
style=3D"TABLE-LAYOUT: fixed; OVERFLOW: hidden; WORD-WRAP: break-word"=20
cellSpacing=3D0 cellPadding=3D0 width=3D"100%" border=3D0 ;>
  <TBODY>
  <TR>
    <TD class=3Dindex vAlign=3Dtop width=3D"5%">2</TD>
    <TD vAlign=3Dtop align=3Dmiddle width=3D"10%">
      <DIV class=3Duser style=3D"OVERFLOW: hidden">
      <SCRIPT language=3Djavascript>
writecmt(2,"d47c5cda400235deb7fd48e2","=C4=E4=C3=FB=CD=F8=D3=D1","","0000=
c4e4c3fbcdf8d3d10000");

</SCRIPT>
      </DIV></TD>
    <TD class=3Dcnt style=3D"PADDING-LEFT: 20px"><SPAN =
class=3Ddate>2008=C4=EA02=D4=C213=C8=D5 =D0=C7=C6=DA=C8=FD=20
      14:59 </SPAN>
      <DIV class=3Ddesc=20
  style=3D"OVERFLOW: hidden; WORD-BREAK: =
normal">=CD=ACls</DIV></TD></TR></TBODY></TABLE>
<DIV class=3Dline></DIV>
<DIV id=3Dpage></DIV></DIV>
<DIV id=3Din_send><A name=3Dsend></A>
<FORM id=3DpopFormSubmit name=3Dform1 onsubmit=3D"return checkcmtform()" =

action=3D/leokan/commit method=3Dpost><INPUT type=3Dhidden value=3D8 =
name=3Dct> <INPUT=20
type=3Dhidden value=3D1 name=3Dcm> <INPUT type=3Dhidden =
value=3D99577bc6a7834e1f9c163d4c=20
name=3DspBlogID>
<SCRIPT language=3DJavaScript>
	document.write("<input type=3D'hidden' name=3D'spRefURL' =
value=3D'"+