Home > OI > Sgu 129

Sgu 129


为这题纠结了两天了……

这题思路很简单,但情 况很多,需细心地一一列举。

1、题目中说,多边形内任意两点连线的中点必在多边形内,因此这是个凸多边形。

2、用类似凸包的 方法,选取最下方的点(若有多个则选取最右边的),以它为基准,对所有点用叉乘进行逆时针排序,这样我们得到了多边形的每一条边。

3、对M 条待测线段分别处理。判断两个端点是否在多边形内。方法是:由点向任意方向作射线,若与多边形的交点为奇数个,则在多边形内,否则在多边形外,对于在多边 形边上的情况要进行特判。由于这个方法特殊情况较多,这里我选用了一种“偷懒”的近似方法:并不真正地取射线,而是在近似无穷远处(此题中我选的是 (23456,34567),当然最好取两个互质的数)取一点,连成线段,再用判断线段相交的方法就行了。

4、计算线段与多边形的 交点,根据交点的数量进行分类讨论。

这题我先是WA on test 2,接着又WA on test 3,然后又WA on test 4,折腾了好久才AC,命苦……

有一些自编数据,希望有所帮助(由于很容易画图,这里只给输入数据)

test1
4
1 1
-1 -1
1 -1
-1 1
8
0 2 2 0
-2 0 2 0
1 1 1 -1
1 1 0 0
1 1 -1 -1
1 1 2 1
-1 3 -1 -3
-1 0 -1 1
——————
test 2
4
3 0
-1 0
0 2
0 -4
2
1 2 0 -4
5 0 -7 8
——————
test 3
6
0 6
-2 3
6 0
3 4
6 -3
0 0
1
6 -3 0 0
——————
test 4
4
0 2
2 0
0 -2
-2 0
1
-4 0 4 0

——————

test 5

4
0 2
2 0
0 -2
-2 0
1
1 3 -2 0

sgu129

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
struct pix
{
double x,y;
} p[401];
struct segs
{
pix a,b;
} seg[1001],edge[1001];
int n,m;
pix c;
double verymin=0.0000001;
inline double abs(double a)
{
return a>=0?a:-a;
}
inline int abs(int a)
{
return a>=0?a:-a;
}
inline double max(double a, double b)
{
return a>b?a:b;
}
inline double min(double a, double b)
{
return a<b?a:b;
}
void swap(pix &a, pix &b)
{
pix x=a;a=b;b=x;
}
void swap(int &a, int &b)
{
int x=a;a=b;b=x;
}
void swap(double &a, double &b)
{
double x=a;a=b;b=x;
}
void init()
{
int id=0;
c.y=99999,c.x=-99999;
scanf(“%d”,&n);
for(int i=1;i<=n;++i)
{
scanf(“%lf%lf”,&p[i].x,&p[i].y);
if(p[i].y<c.y||p[i].y==c.y&&p[i].x>c.x)
{
c.x=p[i].x;
c.y=p[i].y;
id=i;
}
}
pix t=p[id];
p[id]=p[1];
p[1]=t;
scanf(“%d”,&m);
for(int i=1;i<=m;++i)
scanf(“%lf%lf%lf%lf”,&seg[i].a.x,&seg[i].a.y,&seg[i].b.x,&seg[i].b.y);
}
double cross(pix a, pix b, pix c)
{
double x1=a.x-c.x,
y1=a.y-c.y,
x2=b.x-c.x,
y2=b.y-c.y;
return x1*y2-x2*y1;
}
double calcdis(pix a, pix b)
{
return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
}
bool isintersect(segs s1, segs s2)
{
return max(s1.a.x,s1.b.x)>=min(s2.a.x,s2.b.x)
&&max(s2.a.x,s2.b.x)>=min(s1.a.x,s1.b.x)
&&max(s1.a.y,s1.b.y)>=min(s2.a.y,s2.b.y)
&&max(s2.a.y,s2.b.y)>=min(s1.a.y,s1.b.y)
&&cross(s1.a,s2.b,s2.a)*cross(s2.b,s1.b,s2.a)>=0
&&cross(s2.a,s1.b,s1.a)*cross(s1.b,s2.b,s1.a)>=0;
}
bool samepoint(pix a, pix b)
{
return abs(a.x-b.x)<verymin&&abs(a.y-b.y)<verymin;
}
bool iscross(segs s1, segs s2)
{
return isintersect(s1,s2)
&&!samepoint(s1.a,s2.a)
&&!samepoint(s1.b,s2.a)
&&!samepoint(s1.a,s2.b)
&&!samepoint(s1.b,s2.b);
}
pix calccross(pix a,pix b,pix c,pix d, bool &flag)
{
double delta=(b.x-a.x)*(c.y-d.y)-(d.x-c.x)*(a.y-b.y);
pix ans;
if(abs(delta)<verymin)
{
flag=false;
return ans;
}
ans.x=(c.y*d.x-c.x*d.y)*(b.x-a.x)-(a.y*b.x-a.x*b.y)*(d.x-c.x);
ans.x/=delta;
ans.y=(a.y*b.x-a.x*b.y)*(c.y-d.y)-(c.y*d.x-c.x*d.y)*(a.y-b.y);
ans.y/=delta;
return ans;
}
bool ison(pix now, segs s)
{
double x1=s.a.x,x2=s.b.x,y1=s.a.y,y2=s.b.y;
double x=now.x,y=now.y;
return (abs((y1-y)*(x2-x)-(y2-y)*(x1-x))<verymin)&&
(((y1-y)*(y2-y)<=0&&(x1-x)*(x2-x)<=0));
}
int isinside(pix now)
{
int ans=0;
segs tmp;
tmp.a=now;
tmp.b.x=23456;
tmp.b.y=34567;
for(int i=1;i<=n;++i)
{
if(ison(now,edge[i]))
return 0;
if(isintersect(tmp,edge[i]))
++ans;
}
if(ans&1) return -1;
return 1;
}
void dealwith(segs tmpnow)
{
segs now=tmpnow;
int ina=isinside(now.a),
inb=isinside(now.b),
cnum=0,tmpcnum=0;
pix cross[10],tmpcross[10];
if(ina>inb)
{
swap(ina,inb);
swap(now.a,now.b);
}
for(int i=1;i<=n;++i)
if(isintersect(edge[i],now))
{
bool flag=true;
pix tmp=calccross(edge[i].a,edge[i].b,now.a,now.b,flag);
if(flag)
tmpcross[++tmpcnum]=tmp;
}
for(int i=1;i<=tmpcnum;++i)
{
bool flagg=true;
for(int j=i+1;j<=tmpcnum;++j)
if(samepoint(tmpcross[i],tmpcross[j]))
{
flagg=false;
break;
}
if(flagg)
cross[++cnum]=tmpcross[i];
}
if(!cnum)
{
if(ina==-1&&inb==-1)
printf(“%.2lf\n”,calcdis(now.a,now.b));
else
printf(“%.2lf\n”,0.0);
}
else if(cnum==1)
{
if(ina==-1&&inb==1||ina==-1&&inb==0)
printf(“%.2lf\n”,calcdis(now.a,cross[cnum]));
else
printf(“%.2lf\n”,0.0);
}
else if(cnum==2)
{
int ta[2]={0},a=0,tb[2]={0},b=0;
for(int i=1;i<=n;++i)
{
if(ison(cross[1],edge[i]))
ta[a++]=i;
if(ison(cross[2],edge[i]))
tb[b++]=i;
}
for(int i=0;i<a;++i) for(int j=0;j<b;++j)if(ta[i]==tb[j])
{
printf(“%.2lf\n”,0.0);
return;
}
printf(“%.2lf\n”,calcdis(cross[1],cross[2]));
}
else
printf(“%.2lf\n”,0.0);
}
void work()
{
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j)
if(cross(p[i],p[j],c)<0)
swap(p[i],p[j]);
for(int i=1;i<=n;++i)
{
edge[i].a=p[i];
edge[i].b=p[i%n+1];
}
for(int i=1;i<=m;++i)
dealwith(seg[i]);
}
int main()
{
init();
work();
return 0;
}
Categories: OI
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: