随笔-72  评论-126  文章-0  trackbacks-0
http://acm.hdu.edu.cn/showproblem.php?pid=1086

//判断两直线是否相交
#include<stdio.h>
#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
struct point {
    
double x,y;
};
struct line {
    point a,b;
}l[
101];
double xmult(point p1,point p2,point p0){
    
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int dots_inline(point p1,point p2,point p3){
    
return zero(xmult(p1,p2,p3));
}
int same_side(point p1,point p2,line l){
    
return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)>eps;
}
int dot_online_in(point p,line l){
    
return zero(xmult(p,l.a,l.b))&&(l.a.x-p.x)*(l.b.x-p.x)<eps&&(l.a.y-p.y)*(l.b.y-p.y)<eps;
}
int intersect_in(line u,line v){
    
if (!dots_inline(u.a,u.b,v.a)||!dots_inline(u.a,u.b,v.b))
        
return !same_side(u.a,u.b,v)&&!same_side(v.a,v.b,u);
    
return dot_online_in(u.a,v)||dot_online_in(u.b,v)||dot_online_in(v.a,u)||dot_online_in(v.b,u);
}
int main()
{
    
int n,i,j;
    
int cnt;
    
while(scanf("%d",&n),n)
    {
        
for(i=0;i<n;i++) {
            scanf(
"%lf%lf%lf%lf",&l[i].a.x,&l[i].a.y,&l[i].b.x,&l[i].b.y);
        }
        cnt 
= 0;
        
for(i=0;i<n;i++) {
            
for(j=i+1;j<n;j++) {
                cnt 
+= intersect_in(l[i],l[j]);
            }
        }
        printf(
"%d\n",cnt);
    }
    
return 0;
}


http://acm.hdu.edu.cn/showproblem.php?pid=1115
求多边形重心
#include<stdio.h>
#include
<math.h>
#define eps 1e-8
struct point{
    
double x,y;
}p[
1000001];
struct line{point a,b;};

double xmult(point p1,point p2,point p0){
    
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
point intersection(line u,line v){
    point ret
=u.a;
    
double t=((u.a.x-v.a.x)*(v.a.y-v.b.y)-(u.a.y-v.a.y)*(v.a.x-v.b.x))
        
/((u.a.x-u.b.x)*(v.a.y-v.b.y)-(u.a.y-u.b.y)*(v.a.x-v.b.x));
    ret.x
+=(u.b.x-u.a.x)*t;
    ret.y
+=(u.b.y-u.a.y)*t;
    
return ret;
}
point barycenter(point a,point b,point c){
    line u,v;
    u.a.x
=(a.x+b.x)/2;
    u.a.y
=(a.y+b.y)/2;
    u.b
=c;
    v.a.x
=(a.x+c.x)/2;
    v.a.y
=(a.y+c.y)/2;
    v.b
=b;
    
return intersection(u,v);
}
point barycenter(
int n,point* p){
    point ret,t;
    
double t1=0,t2;
    
int i;
    ret.x
=ret.y=0;
    
for (i=1;i<n-1;i++)
        
if (fabs(t2=xmult(p[0],p[i],p[i+1]))>eps){
            t
=barycenter(p[0],p[i],p[i+1]);
            ret.x
+=t.x*t2;
            ret.y
+=t.y*t2;
            t1
+=t2;
        }
        
if (fabs(t1)>eps)
            ret.x
/=t1,ret.y/=t1;
        
return ret;
}

int main()
{
    
int T,i,n;
    scanf(
"%d",&T);
    
while(T--)
    {
        scanf(
"%d",&n);
        
for(i=0;i<n;i++) {
            scanf(
"%lf%lf",&p[i].x,&p[i].y);
        }
        point x 
= barycenter(n,p);
        x.x 
+= eps;
        x.y 
+= eps;
        printf(
"%.2lf %.2lf\n",x.x,x.y);
    }
}


http://acm.hdu.edu.cn/showproblem.php?pid=2671
//点关于直线的对称点

#include
<stdio.h>
#include
<math.h>
#define eps 1e-8
struct point{
    
double x,y;
};
struct line{
    point a,b;
};


double dis(point p1,point p2) {
    
return sqrt( (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) );
}
double xmult(point p1,point p2,point p0){
    
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int same_side(point p1,point p2,line l){
    
return xmult(l.a,p1,l.b)*xmult(l.a,p2,l.b)>eps;
}
point intersection(point u1,point u2,point v1,point v2){
    point ret
=u1;
    
double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
            
/((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
    ret.x
+=(u2.x-u1.x)*t;
    ret.y
+=(u2.y-u1.y)*t;
    
return ret;
}
point ptoline(point p,line l){
    point t
=p;
    t.x
+=l.a.y-l.b.y;
    t.y
+=l.b.x-l.a.x;
    
return intersection(p,t,l.a,l.b);
}


int main()
{
    
int T;
    
double k;
    point a,b,c,d;
    line cd;
    scanf(
"%d",&T);
    
while(T--)
    {
        scanf(
"%lf",&k);
        scanf(
"%lf%lf%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y,&c.x,&c.y);
        d.x 
= c.x + 1;
        d.y 
= c.y + 1*k;
        cd.a 
= c;
        cd.b 
= d;
        
if(same_side(a,b,cd)) {
            point e 
= ptoline(a,cd);
            a.x 
= a.x + (e.x-a.x)*2;
            a.y 
= a.y + (e.y-a.y)*2;
        }
        printf(
"%.2lf\n",dis(a,b));
    }
}

http://acm.hdu.edu.cn/showproblem.php?pid=1700

//一个点绕另外一个点旋转并扩大
#include<stdio.h>
#include 
<math.h>
struct point{double x,y;};

point rotate(point v,point p,
double angle,double scale){
    point ret
=p;
    v.x
-=p.x,v.y-=p.y;
    p.x
=scale*cos(angle);
    p.y
=scale*sin(angle);
    ret.x
+=v.x*p.x-v.y*p.y;
    ret.y
+=v.x*p.y+v.y*p.x;
    
return ret;
}
int main()
{
    
int T;
    point a,o,b,c;
    o.x 
= 0;
    o.y 
= 0;
    scanf(
"%d",&T);
    
while(T--)
    {
        scanf(
"%lf%lf",&a.x,&a.y);
        b 
= rotate(a,o,120.0/180*acos(-1.0),1);
        c 
= rotate(a,o,-120.0/180*acos(-1.0),1);
        
if(b.y<c.y || b.y==c.y && b.x<c.x)
            printf(
"%.3lf %.3lf %.3lf %.3lf\n",b.x,b.y,c.x,c.y);
        
else
            printf(
"%.3lf %.3lf %.3lf %.3lf\n",c.x,c.y,b.x,b.y);
    }
    
return 0;
}


http://acm.hdu.edu.cn/showproblem.php?pid=1756
//判点在任意多边形内,顶点按顺时针或逆时针给出
//on_edge表示点在多边形边上时的返回值,offset为多边形坐标上限

#include 
<stdio.h>
#include 
<stdlib.h>
#include 
<math.h>
#define offset 1000
#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
#define _sign(x) ((x)>eps?1:((x)<-eps?2:0))
struct point{double x,y;};
double xmult(point p1,point p2,point p0){
    
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
int inside_polygon(point q,int n,point* p,int on_edge=1){
    point q2;
    
int i=0,count;
    
while (i<n)
        
for (count=i=0,q2.x=rand()+offset,q2.y=rand()+offset;i<n;i++)
            
if (zero(xmult(q,p[i],p[(i+1)%n]))&&(p[i].x-q.x)*(p[(i+1)%n].x-q.x)<eps&&(p[i].y-q.y)*(p[(i+1)%n].y-q.y)<eps)
                
return on_edge;
            
else if (zero(xmult(q,q2,p[i])))
                
break;
            
else if (xmult(q,p[i],q2)*xmult(q,p[(i+1)%n],q2)<-eps&&xmult(p[i],q,p[(i+1)%n])*xmult(p[i],q2,p[(i+1)%n])<-eps)
                count
++;
            
return count&1;
}
int main()
{
    
int n,m,i;
    point p[
101],q;
    
while(scanf("%d",&n)==1)
    {
        
for(i=0;i<n;i++)
            scanf(
"%lf%lf",&p[i].x,&p[i].y);
        scanf(
"%d",&m);
        
while(m--)
        {
            scanf(
"%lf%lf",&q.x,&q.y);
            puts(inside_polygon(q,n,p)
?"Yes":"No");
        }
    }
    
return 0;
}

内容及代码日后补充整理。。。。。
posted on 2009-03-11 13:57 shǎ崽 阅读(952) 评论(4)  编辑 收藏 引用

评论:
# re: 一些计算几何基础公式 2009-03-11 17:51 | fdar
期待  回复  更多评论
  
# re: 一些计算几何基础公式 2009-03-12 13:29 | AekdyCoin
Orz
ym  回复  更多评论
  
# re: 一些计算几何基础公式 2009-03-12 15:29 | fdar
Orz是啥意思。。  回复  更多评论
  
# re: 一些计算几何基础公式 2009-03-12 15:41 | shǎ崽
本来整理自己看的
几何知识一点都不会
。。。唉
被大牛们嘲笑了  回复  更多评论
  

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