首页 > ACM题库 > HDU-杭电 > hdu 2797 Doors And Preguins-计算几何-[解题报告]hoj
2014
02-14

hdu 2797 Doors And Preguins-计算几何-[解题报告]hoj

Doors And Preguins

问题描述 :

The organizers of the Annual Computing Meeting have invited a number of vendors to set up booths in a large exhibition hall during the meeting to showcase their latest products. As the vendors set up their booths at their assigned locations, they discovered that the organizers did not take into account an important fact—each vendor supports either the Doors operating system or the Penguin operating system, but not both. A vendor supporting one operating system does not want a booth next to one supporting another operating system.

Unfortunately the booths have already been assigned and even set up. There is no time to reassign the booths or have them moved. To make matter worse, these vendors in fact do not even want to be in the same room with vendors supporting a different operating system.

Luckily, the organizers found some portable partition screens to build a wall that can separate the two groups of vendors. They have enough material to build a wall of any length. The screens can only be used to build a straight wall. The organizers need your help to determine if it is possible to separate the two groups of vendors by a single straight wall built from the portable screens. The wall built must not touch any vendor booth (but it may be arbitrarily close to touching a booth). This will hopefully prevent one of the vendors from knocking the wall over accidentally.

输入:

There are multiple cases (no more than 100).

The input consists of a number of cases. Each case starts with 2 integers on a line separated by a single space: D and P, the number of vendors supporting the Doors and Penguins operating system, respectively (1 <= D, P <= 500). The next D lines specify the locations of the vendors supporting Doors. This is followed by P lines specifying the locations of the vendors supporting Penguins. The location of each vendor is specified by four positive integers: x1, y1, x2, y2. (x1, y1) specifies the coordinates of the southwest corner of the booth while (x2, y2) specifies the coordinates of the northeast corner. The coordinates satisfy x1 < x2 and y1 < y2. All booths are rectangular and have sides parallel to one of the compass directions. The coordinates of the southwest corner of the exhibition hall is (0,0) and the coordinates of the northeast corner is (15000, 15000). You may assume that all vendor booths are completely inside the exhibition hall and do not touch the walls of the hall. The booths do not overlap or touch each other.

The end of input is indicated by D = P = 0.

输出:

There are multiple cases (no more than 100).

The input consists of a number of cases. Each case starts with 2 integers on a line separated by a single space: D and P, the number of vendors supporting the Doors and Penguins operating system, respectively (1 <= D, P <= 500). The next D lines specify the locations of the vendors supporting Doors. This is followed by P lines specifying the locations of the vendors supporting Penguins. The location of each vendor is specified by four positive integers: x1, y1, x2, y2. (x1, y1) specifies the coordinates of the southwest corner of the booth while (x2, y2) specifies the coordinates of the northeast corner. The coordinates satisfy x1 < x2 and y1 < y2. All booths are rectangular and have sides parallel to one of the compass directions. The coordinates of the southwest corner of the exhibition hall is (0,0) and the coordinates of the northeast corner is (15000, 15000). You may assume that all vendor booths are completely inside the exhibition hall and do not touch the walls of the hall. The booths do not overlap or touch each other.

The end of input is indicated by D = P = 0.

样例输入:

3 3
10 40 20 50
50 80 60 90
30 60 40 70
30 30 40 40
50 50 60 60
10 10 20 20
2 1
10 10 20 20
40 10 50 20
25 12 35 40
0 0

样例输出:

Case 1: It is possible to separate the two groups of vendors.

Case 2: It is not possible to separate the two groups of vendors.


题目描述:现在又两种长方形(每种最多500个),问能否用一条线将这两种长方形分开,并且长方形不允许和那条线有交点。解法:看到时觉得挺难,其实还是蛮简单的。我是这样做的,首先把长方形的四个顶点都拿出来,然后对两种长方形分别求凸包,然后判定两个凸包是否有交点,如果有交点就是不可以的(不一定要相交的面积为0哦!!),否则就是可以的。我的代码可能有点乱,不过还是贴上吧!方便自己学些。代码:#include<iostream>#include<algorithm>#include<math.h>using namespace std;const int Maxn = 2005;const double eps = 1e-10;typedef struct TPodouble {double x;double y;}TPoint;typedef struct TPolygon{TPoint p[Maxn];int n;};typedef struct TLine{double a, b, c;}TLine;int D,P;TPoint tmp;TPoint stack[Maxn];bool same(TPoint p1, TPoint p2){if(p1.x != p2.x) return false;if(p1.y != p2.y) return false;return true;}double multi(TPoint p1, TPoint p2, TPoint p0){//求矢量[p0, p1], [p0, p2]的叉积//p0是顶点 return (p1.x – p0.x) * (p2.y – p0.y) – (p2.x – p0.x) * (p1.y – p0.y);//若结果等于0,则这三点共线//若结果大于0,则p0p2在p0p1的逆时针方向//若结果小于0,则p0p2在p0p1的顺时针方向 }TLine lineFromSegment(TPoint p1, TPoint p2){//线段所在直线,返回直线方程的三个系统 TLine tmp;tmp.a = p2.y – p1.y;tmp.b = p1.x – p2.x;tmp.c = p2.x * p1.y – p1.x * p2.y;return tmp;}TPoint LineInter(TLine l1, TLine l2){//求两直线得交点坐标TPoint tmp; double a1 = l1.a;double b1 = l1.b;double c1 = l1.c;double a2 = l2.a;double b2 = l2.b;double c2 = l2.c;//注意这里b1 = 0 if(fabs(b1) < eps){tmp.x = -c1 / a1;  tmp.y = (-c2 – a2 * tmp.x) / b2;}       else{tmp.x = (c1 * b2 – b1 * c2) / (b1 * a2 – b2 * a1);tmp.y = (-c1 – a1 * tmp.x) / b1;}return tmp;}TPolygon Cut_polygon(TPoint p1, TPoint p2, TPolygon polygon){TPolygon new_polygon;TPoint interp;TLine l1, l2;int i, j;double t1, t2;new_polygon.n = 0;for(i = 0;i <= polygon.n – 1;i++){t1 = multi(p2, polygon.p[i], p1);t2 = multi(p2, polygon.p[i + 1], p1);if(fabs(t1) < eps || fabs(t2) < eps){if(fabs(t1) < eps) new_polygon.p[new_polygon.n++] = polygon.p[i];    if(fabs(t2) < eps) new_polygon.p[new_polygon.n++] = polygon.p[i + 1];}else if(t1 < 0 && t2 < 0){new_polygon.p[new_polygon.n++] = polygon.p[i];    new_polygon.p[new_polygon.n++] = polygon.p[i + 1];}else if(t1 * t2  < 0){l1 = lineFromSegment(p1, p2);l2 = lineFromSegment(polygon.p[i], polygon.p[i + 1]);interp = LineInter(l1, l2);    if(t1 < 0) {new_polygon.p[new_polygon.n++] = polygon.p[i];new_polygon.p[new_polygon.n++] = interp;}else {new_polygon.p[new_polygon.n++] = interp;new_polygon.p[new_polygon.n++] = polygon.p[i + 1];        }}}polygon.n = 0;if(new_polygon.n == 0) return polygon;polygon.p[polygon.n++] = new_polygon.p[0];for(i = 1;i < new_polygon.n;i++){if(!same(new_polygon.p[i], new_polygon.p[i - 1])){polygon.p[polygon.n++] = new_polygon.p[i];}    }if(polygon.n != 1 && same(polygon.p[polygon.n - 1], polygon.p[0])) polygon.n–;polygon.p[polygon.n] = polygon.p[0];return polygon;}TPolygon polygon_d,polygon_p;bool readIn(){scanf("%d%d",&D,&P);if(D==0&&P==0) return false;polygon_d.n=0,polygon_p.n=0;double x1,y1,x2,y2;int j=0;for(int i=0;i<D;i++){scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);polygon_d.p[j].x=x1,polygon_d.p[j].y=y1;j++;polygon_d.p[j].x=x1,polygon_d.p[j].y=y2;j++;polygon_d.p[j].x=x2,polygon_d.p[j].y=y1;j++;polygon_d.p[j].x=x2,polygon_d.p[j].y=y2;j++;}polygon_d.n=j;j=0;for(int i=0;i<P;i++){scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);polygon_p.p[j].x=x1,polygon_p.p[j].y=y1;j++;polygon_p.p[j].x=x1,polygon_p.p[j].y=y2;j++;polygon_p.p[j].x=x2,polygon_p.p[j].y=y1;j++;polygon_p.p[j].x=x2,polygon_p.p[j].y=y2;j++;}polygon_p.n=j;return true;}double dis(TPoint p1, TPoint p2){return (p1.x – p2.x) * (p1.x – p2.x) + (p1.y – p2.y) * (p1.y – p2.y);}bool cmp(TPoint c, TPoint d){double k = multi(c, d,tmp);if(k > eps) return true;else if(fabs(k) <= eps && dis(c, tmp) <= dis(d, tmp)) return true;else return false;   }void get_grahamscan(TPolygon &poly){int cur = 0;for(int i=1;i<poly.n;i++){if(poly.p[cur].x>poly.p[i].x||poly.p[cur].x==poly.p[i].x&&poly.p[cur].y>poly.p[i].y)cur = i;}swap(poly.p[cur],poly.p[0]);tmp = poly.p[0];sort(poly.p+1,poly.p+poly.n,cmp);int top , i;for(i = 0;i <= 2;i++) stack[i] = poly.p[i];top = 2;for(i = 3;i < poly.n;i++){while(multi(poly.p[i], stack[top], stack[top - 1]) >= 0){top–;if(top == 0)break;}top++;stack[top] = poly.p[i];}int size = top;int j = top;for(int i=0;i<=top;i++)poly.p[j--] = stack[i];poly.p[top+1]=poly.p[0];poly.n=size+1;}bool check(TPoint p1,TPoint p2,TPoint p0){return fabs(multi(p1,p2,p0))<=eps&&(min(p1.x,p2.x)<=p0.x&&p0.x<=max(p1.x,p2.x)&&min(p1.y,p2.y)<=p0.y&&p0.y<=max(p1.y,p2.y));}bool Solve(){get_grahamscan(polygon_p);get_grahamscan(polygon_d);for(int i=0;i<polygon_p.n;i++){for(int j=0;j<polygon_d.n;j++){if(check(polygon_d.p[j],polygon_d.p[j+1],polygon_p.p[i])) return false;    }}for(int i=0;i<polygon_d.n;i++){for(int j=0;j<polygon_p.n;j++){if(check(polygon_p.p[j],polygon_p.p[j+1],polygon_d.p[i]))return false;    }}for(int i=0;i<polygon_p.n;i++){polygon_d = Cut_polygon(polygon_p.p[i],polygon_p.p[i+1],polygon_d);if(polygon_d.n<3) return true;    }return false;}int main(){int mm = 0;while(readIn()){if( mm > 0 ) printf("\n");if(D==0||P==0){printf("Case %d: It is possible to separate the two groups of vendors.\n",++mm);    } else {if(Solve()) printf("Case %d: It is possible to separate the two groups of vendors.\n",++mm);else printf("Case %d: It is not possible to separate the two groups of vendors.\n",++mm);    }}}
解题参考:http://hi.baidu.com/happy457/item/08c76fd0cc65f1f2cb0c39f2


  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  2. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge