T9的空间

You will never walk alone!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  69 随笔 :: 0 文章 :: 28 评论 :: 0 Trackbacks

判断两个凸多边形是否相交。做比赛的时候没有判断是否两个多边形可以包含,wa!贴上去当作模板吧

  1#include<iostream>
  2#include<algorithm>
  3#include<cmath>
  4using namespace std;
  5
  6const int oo=0x7fffffff;
  7const double eps=1e-6;
  8
  9void pass() {cout<<"passpasspasspass"<<endl;}
 10template<class T> void print (T a) {cout<<a<<endl;}
 11template<class T> void print (T a,int n) {for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl;}
 12template<class T> T gmax(T a,T b) {return a>b?a:b;}
 13template<class T> T gmin(T a,T b) {return a>b?b:a;}
 14template<class T> T square (T a) {return a*a;}
 15
 16const int MaxP=2005;
 17
 18//平面点
 19typedef struct TPoint
 20{
 21    double x,y;
 22    TPoint(double _x=0.0,double _y=0.0):x(_x),y(_y){}
 23}
TPoint;
 24
 25TPoint p0;
 26int ch[2005];
 27int top;
 28
 29//平面直线(非方程)
 30typedef struct Line1
 31{
 32    TPoint s;
 33    TPoint e;
 34    Line1(TPoint _s,TPoint _e):s(_s),e(_e){}
 35}
Line1;
 36
 37//平面多边形
 38typedef struct Poly
 39{
 40    TPoint p[MaxP];
 41    int n;
 42}
Poly;
 43
 44//平面点的距离
 45double dist(TPoint a,TPoint b)
 46{
 47    return square(a.x-b.x)+square(a.y-b.y);
 48}

 49
 50//p0p1 cross p0p2
 51double cross(TPoint p0,TPoint p1,TPoint p2)
 52{
 53    return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x);
 54}

 55
 56
 57//两条直线是否相交
 58bool isins(TPoint s1,TPoint e1,TPoint s2,TPoint e2)
 59{
 60    if(gmax(s1.x,e1.x)>=gmin(s2.x,e2.x)&& 
 61        gmax(s2.x,e2.x)>=gmin(s1.x,e1.x)&&
 62        gmax(s1.y,e1.y)>=gmin(s2.y,e2.y)&&
 63        gmax(s2.y,e2.y)>=gmin(s1.y,e1.y)&&
 64        cross(s1,s2,e1)*cross(s1,e1,e2)>=0&&
 65        cross(s2,s1,e2)*cross(s2,e2,e1)>=0)
 66        return true;
 67    else return false;
 68}

 69
 70//判断点是否在多边形内部利用面积是否相等
 71bool inpoly(TPoint p,Poly a)
 72{
 73    int i,area1=0,area2=0;
 74    a.p[a.n]=a.p[0];//把p0给pn,便于循环
 75    for(i=0;i<a.n;i++)
 76        area1+=fabs(cross(p,a.p[i],a.p[i+1]));
 77    for(i=1;i<a.n-1;i++)
 78        area2+=fabs(cross(a.p[0],a.p[i],a.p[i+1]));
 79    if(fabs(area1-area2)<eps)return true;
 80    else return false;
 81}

 82//判断凸多边形是否相交
 83bool ins(Poly &a,Poly &b)
 84{
 85    a.p[a.n]=a.p[0];
 86    b.p[b.n]=b.p[0];
 87    int i,j;
 88    for(i=0;i<a.n;i++)
 89        for(j=0;j<b.n;j++)
 90            if(isins(a.p[i],a.p[i+1],b.p[j],b.p[j+1]))
 91                return true;
 92    if(inpoly(a.p[0],b)||inpoly(b.p[0],a))
 93        return true;
 94    return false;
 95}

 96
 97//graham扫描法求凸包
 98bool cmp(TPoint a,TPoint b)
 99{
100    double c=cross(p0,a,b);
101    if(c>0)return true;
102    else if(!c&&dist(p0,b)<dist(p0,a))
103        return true;
104    else return false;
105}

106
107void graham(TPoint p[],int n)
108{
109    int i,se=0;
110    for(i=0;i<n;i++)
111        if(p[i].y<p[se].y||(p[i].y==p[se].y&&p[i].x<p[se].x))
112            se=i;
113    swap(p[se],p[0]);
114    p0=p[0];
115    sort(p+1,p+n,cmp);
116    for(i=0;i<=1;i++) ch[i]=i;
117    top=1;
118    for(i=2;i<n;i++)
119    {
120        while(cross(p[ch[top-1]],p[ch[top]],p[i])<=0)
121        {
122            if(top==1)break;
123            top--;
124        }

125        ch[++top]=i;
126    }

127}

128
129
130TPoint p[MaxP];
131
132int main()
133{
134    int T=1,i,n;
135    double X1,Y1,X2,Y2;
136    int D,P;
137    while(scanf("%d%d",&D,&P)&&(D||P))
138    {
139        for(i=0,n=0;i<D;i++)
140        {
141            scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2);
142            p[n].x=X1; p[n++].y=Y1;
143            p[n].x=X2; p[n++].y=Y1;
144            p[n].x=X2; p[n++].y=Y2;
145            p[n].x=X1; p[n++].y=Y2;
146        }

147        Poly d;
148        graham(p,n);
149        for(i=0;i<=top;i++)
150            d.p[i]=p[ch[i]];
151        d.n=top+1;
152
153        for(i=0,n=0;i<P;i++)
154        {
155            scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2);
156            p[n].x=X1; p[n++].y=Y1;
157            p[n].x=X2; p[n++].y=Y1;
158            p[n].x=X2; p[n++].y=Y2;
159            p[n].x=X1; p[n++].y=Y2;
160        }

161        Poly pe;
162        graham(p,n);
163        for(i=0;i<=top;i++)
164            pe.p[i]=p[ch[i]];
165        pe.n=top+1;
166
167        if(ins(d,pe))
168            printf("Case %d: It is not possible to separate the two groups of vendors.\n\n",T++);
169        else 
170            printf("Case %d: It is possible to separate the two groups of vendors.\n\n",T++);
171    }

172    return 0;
173}
posted on 2008-09-07 12:51 Torres 阅读(332) 评论(0)  编辑 收藏 引用 所属分类: Computation Geometry

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理