思路挺简单，就是检查其它点是否在两点连线的中间，如果在就被挡住了，其它的情况就是没被挡住。另外需要提前检查相对最远距离的大小关系，更详细的自行看代码，写得也不怎么罗嗦。#include<iostream>using std::cout;using std::cin;using std::endl;int main(int argc,char *argv[]){#define MIN_E 展开
思路挺简单，就是检查其它点是否在两点连线的中间，如果在就被挡住了，其它的情况就是没被挡住。另外需要提前检查相对最远距离的大小关系，更详细的自行看代码，写得也不怎么罗嗦。#include<iostream>using std::cout;using std::cin;using std::endl;int main(int argc,char *argv[]){#define MIN_ERROR (0.00001)int groupnum,i,curx[101],cury[101],*outmark;char outstr[2][16]={"NO","YES"};cin >>groupnum;outmark = new int[groupnum];for(i=0;i<groupnum ;++i){int linenum,maxdist,j,basedx,basedy;double bscale;cin >>linenum >>maxdist;for(j=0;j<linenum;++j)cin >>curx[j] >>cury[j];outmark[i] = 1;basedx = curx[linenum-1]-curx[0];basedy = cury[linenum-1]-cury[0];if( (basedx*basedx+basedy*basedy) >(maxdist*maxdist) ){outmark[i] = 0;continue;}if( linenum<3 ) continue;if( basedx && basedy )bscale = (double)basedy/(double)basedx;for(j=1;j<linenum-1;++j){int curdx=curx[j]-curx[0],curdy=cury[j]-cury[0];if( ( 0==basedx && 0==curdx && ( curdy*(cury[linenum-1]-cury[j])>0 ) ) ||( 0==basedy && 0==curdy && ( curdx*(curx[linenum-1]-curx[j])>0 ) )){outmark[i] = 0;break;}else{double subv;/* assure relate point in middle */if( curdx*(curx[linenum-1]-curx[j])<0 || curdy*(cury[linenum-1]-cury[j])<0 ) continue;subv = bscale-(double)curdy/(double)curdx;if( subv<0 ) subv=-subv;if( subv<MIN_ERROR ){outmark[i] = 0;break;}}}}for(i=0;i<groupnum ;++i)cout <<outstr[outmark[i]] <<endl;delete []outmark;return(0);} 收起
