UVA 1398 Meteor

目测佳哥书上几何那的题,今天一看才知道没那么难,一做才知道没那么简单。

判断射线是否穿过矩形,可以采用这种办法:

求出所有可行的交点,其中矩形顶点要算2次,

对交点去重,如果剩下2个点,那么是穿过的。

另外必须注意的是,如果开始点在矩形内,需要当作一个“交点”,这里是一个易错点。

其实求得交点是用时间来表示的。

那么时间小的必然是穿入点,时间大的必然是穿出点。以此作为两个事件点,一个为+1,一个为-1。

求出所有射线与矩形相交的时间后,对事件按时间排序,然后扫描一遍求出最大值即可。

另外有两个小技巧,一个是代码中的,同一时间的事件点(有这样数据)需要求和,而不能一个一个计算。

另外一个技巧就是对时间相同的事件点,按照先出后进,就可以一个一个计算。

#include #include #include #include #include #include #include #include #include using namespace std; const int X=60; const double sqt2=sqrt(0.5); const double eps=1e-8; const double pi=3.14159265358979323; struct point{ double x,y,vx,vy; point(){} point(double xx,double yy){ x=xx;y=yy; } }a; point operator +(point a,point b){ return point(a.x+b.x,a.y+b.y); } point operator -(point a,point b){ return point(a.x-b.x,a.y-b.y); } point operator *(point a,double b){ return point(a.x*b,a.y*b); } point operator /(point a,double b){ return point(a.x/b,a.y/b); } int sign(double x){ return xeps; } bool operator =0&& sign(a.y-max(b.y,c.y))=0; } struct event{ double t; int sign; }e[1000100]; double w,h; int top; bool in(double x,double y){ return sign(x)>0&&sign(x-w)0&&sign(y-h)=0&&sign(y)>=0&&sign(y-h)=0&&sign(y)>=0&&sign(y-h)=0&&sign(x)>=0&&sign(x-w)=0&&sign(x)>=0&&sign(x-w)

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:hdu3639Hawk-and-Chicken
下一篇:hdu1054 Strategic Game---二分图匹配
相关文章

Uva 10152 ShellSort

uva 297 Quadtrees

uva 572 - Oil Deposits

uva 548 Tree

uva 439 - Knight Moves

UVa 10004 - Bicoloring

uva 10054 - The Necklace

uva 10012 How Big Is It?

UVa 565 - Pizza Anyone?

UVa 704 - Colour Hash, 双向bfs

图文推荐

UVA 1398 Meteor
ZOJ 3640 Help Me
UVA 1398 Meteor
CF 518C(Anya and
UVA 1398 Meteor
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2015-02-26 人气:6
本文关键词:
分享到:

相关文章

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.065 (s). 10 q(s)