URAL 1215 Exactness of Projectile Hit 【点到线段的距离和点在多边形内与否的判断】

题目链接:http://acm.timus.ru/problem.aspx?space=1&num=1215

坑爹的题,让我交了17次才过。。。。这。。
几个关键点。(判断点在“凸”多边形内,果断用叉积判断而非“角和”判断吧。我不知道ural怎么做到的,我把eps开到了1都能把我的“角和”判断卡掉,太nb了。)
1.叉积判断点在多边形内或上
如果旋转叉积过程中出现“正”以及“负”号情况发生,则点在“凸”多边形外。前提,点按顺/逆时针给出。
2.点到线段的距离
根据点积判断点与线段两端点组成的三角形的两个底角(相对于用于判断的点而言)是否均非钝角。
若有一个钝角,则点到线段的距离为点到两端点距离中的小者;若无,则为垂足距离。

(自己写的几何模板不要偷懒。。能用向量绝不解析。。。不然卡精度卡死你。。还有,有标准做法的,千万不要用偷懒做法水过去,不然以后会后悔的)
附代码:
#include <iostream>
#include 
<cstdio>
#include 
<cmath>
#define sqr(x) ((x) * (x))
using namespace std;
#define maxn 105
const double eps = 1e-6;
const double pi = acos(-1.0);
int comp(double x)
{
    
if(fabs(x) < eps)
        
return 0;
    
else if(x < -eps)
        
return -1;
    
else
        
return 1;
}
struct point
{
    
int x,y;
    point(){}
    point(
int a,int b):x(a),y(b){}
    point 
operator -(const point &p)
    {
        
return point(x - p.x,y - p.y);
    }
    
int operator *(const point &p)
    {
        
return x * p.x + y * p.y;
    }
    
int operator ^(const point &p)
    {
        
return x * p.y - y * p.x;
    }
    
int norm2()
    {
        
return sqr(x) + sqr(y);
    }
}p[maxn],o;
int multi(point a,point b,point o)
{
    
return (a - o) ^ (b - o);
}
int scalar(point a,point b,point o)
{
    
return (a - o) * (b - o);
}
int n;
int main()
{
    
int a,b;
    scanf(
"%d %d",&a,&b);
    o 
= point(a,b);
    scanf(
"%d",&n);
    
for(int i = 0;i < n;i++)
    {
        scanf(
"%d %d",&a,&b);
        p[i] 
= point(a,b);
    }
    
bool pos = false,neg = false;
    
for(int i = 0;i < n;i++)
    {
        
int a = i,b = (i + 1% n;
        
int flag = multi(p[a],p[b],o);
        
if(flag > 0 && !pos)
            pos 
= true;
        
if(flag < 0 && !neg)
            neg 
= true;
    }
    
if(!(neg && pos))
    {
        printf(
"%.3lf\n",0.0);
        
return 0;
    }
    
double r = 1e10;
    
for(int i = 0;i < n;i++)
    {
        
int a = i,b = (i + 1% n;
        
double lab = sqrt((double)(p[a] - p[b]).norm2()),lbo = sqrt((double)(o - p[b]).norm2()),lao = sqrt((double)(o - p[a]).norm2());
        
int sbao = scalar(p[b],o,p[a]),sabo = scalar(p[a],o,p[b]);
        
double bao = acos((double) sbao / (lab * lao)),abo = acos((double)sabo / ( lab * lbo));
        
if(comp(bao - pi / 2.0<= 0 && comp(abo - pi / 2.0<= 0)
            r 
= min(r,fabs((double)multi(p[a],p[b],o)) / lab);
        
else
            r 
= min(r,min(lbo,lao));
    }
    printf(
"%.3lf\n",r * 2.0);
}

posted on 2011-08-19 21:30 BUPT-[aswmtjdsj] @ Penalty 阅读(271) 评论(0)  编辑 收藏 引用 所属分类: 计算几何Ural Solution Report


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年8月>
31123456
78910111213
14151617181920
21222324252627
28293031123
45678910

导航

统计

常用链接

留言簿(1)

随笔分类(150)

随笔档案(71)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜