题目大意是给出一个n边形各个点的坐标，接下来有m个询问，回答每个询问中的点是否在n边形内。
这是最基本的计算几何题了，一般有两种方法：射线法和环顾法（又称转角法）。虽然两者的时间复杂度都是线性的，但环顾法要慢很多。而射线法实现时并不需要真的设一个极远的端点来利用判断线段相交的方法判断是否有交点，只需利用快速排斥实验的原理以及叉积的特性即可，规定只有在某一边的计算穿点数。在这一题中我对于穿越端点的处理方法是不对其进行计数处理，但实际上可以构造出数据使我的程序出错，更为严谨的方法应该是特判或者用平移法将其平移一段很小的距离（参见黑书上的具体说明）。另外如果点在n边形的端点或边上可直接判定在形内。
2998704 2008-07-23 13:42:44 Accepted 1081 FPC 00:00.00 408K IwfWcf
博文
toms outlet, http://www.tomsoutlet-stores.com/
回复删除nike roshe, http://www.nikerosherunshoes.co.uk/
prada handbags, http://www.pradahandbagsoutlet.co.uk/
soccer jerseys, http://www.cheapsoccerjersey.net/
michael kors outlet store, http://www.michaelkorsoutlet-store.us.com/
true religion jeans, http://www.truereligionjeansoutlets.us.com/
oakley sunglasses, http://www.oakleysunglasses-outlet.us.com/
nike free 5, http://www.nikefree5.us/
louis vuitton bags, http://www.louisvuittonbag.us.com/
chanel handbags, http://www.chanelhandbags-outlet.co.uk/
chanel handbags, http://www.chanelhandbags-outlet.us.com/
louis vuitton handbags, http://www.louisvuittonhandbag.us/
louis vuitton outlet, http://www.louisvuittonoutlet.in.net/
ghd hair straighteners, http://www.ghdhairstraightenerssale.co.uk/
nba jerseys, http://www.nbajerseys.us.com/
coach outlet, http://www.coachoutletstores.com.co/
true religion jeans, http://www.truereligionjeanscanada.com/
swarovski crystal, http://www.swarovskicrystals.co.uk/
mbt shoes, http://www.mbtshoesoutlet.us.com/
michael kors handbags, http://www.michaelkorshandbags.in.net/
chanel handbags, http://www.chanelhandbagsoutlet.in.net/
michael kors outlet online, http://www.michaelkorsoutletonline.in.net/
polo ralph lauren, http://www.poloralphlauren.us.org/
the north face clearance, http://www.thenorthfaceclearances.us.com/
jordan shoes, http://www.jordan-shoes.us.com/
beats by dr dre, http://www.beatsbydrdre-headphones.us.com/
the north face uk, http://www.thenorthfaces.org.uk/
1003maoqiuyun
Get More Info replica designer bags wholesale go to these guys replica wallets get redirected here replica gucci
回复删除