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ǎ崽 閱讀(1000)
評論(4) 編輯 收藏 引用