[POJ 3449] Geometric Shapes【计算几何】

  • 2017-12-23
  • 0
  • 0

Problem:

Time Limit: 2000MS Memory Limit: 65536K

Description

While creating a customer logo, ACM uses graphical utilities to draw a picture that can later be cut into special fluorescent materials. To ensure proper processing, the shapes in the picture cannot intersect. However, some logos contain such intersecting shapes. It is necessary to detect them and decide how to change the picture.

Given a set of geometric shapes, you are to determine all of their intersections. Only outlines are considered, if a shape is completely inside another one, it is not counted as an intersection.

Input

Input contains several pictures. Each picture describes at most 26 shapes, each specified on a separate line. The line begins with an uppercase letter that uniquely identifies the shape inside the corresponding picture. Then there is a kind of the shape and two or more points, everything separated by at least one space. Possible shape kinds are:

• square: Followed by two distinct points giving the opposite corners of the square.
• rectangle: Three points are given, there will always be a right angle between the lines connecting the first point with the second and the second with the third.
• line: Specifies a line segment, two distinct end points are given.
• triangle: Three points are given, they are guaranteed not to be co-linear.
• polygon: Followed by an integer number N (3 ≤ N ≤ 20) and N points specifying vertices of the polygon in either clockwise or anti-clockwise order. The polygon will never intersect itself and its sides will have non-zero length.

All points are always given as two integer coordinates X and Y separated with a comma and enclosed in parentheses. You may assume that |X|, |Y | ≤ 10000.

The picture description is terminated by a line containing a single dash (“-”). After the last picture, there is a line with one dot (“.”).

Output

For each picture, output one line for each of the shapes, sorted alphabetically by its identifier (X). The line must be one of the following:

• “X has no intersections”, if X does not intersect with any other shapes.
• “X intersects with A”, if X intersects with exactly 1 other shape.
• “X intersects with A and B”, if X intersects with exactly 2 other shapes.
• “X intersects with A, B, . . ., and Z”, if X intersects with more than 2 other shapes.

Please note that there is an additional comma for more than two intersections. A, B, etc. are all intersecting shapes, sorted alphabetically.

Print one empty line after each picture, including the last one.

Sample Input

A square (1,2) (3,2)
F line (1,3) (4,4)
W triangle (3,5) (5,5) (4,3)
X triangle (7,2) (7,4) (5,3)
S polygon 6 (9,3) (10,3) (10,4) (8,4) (8,1) (10,2)
B rectangle (3,3) (7,5) (8,3)
-
B square (1,1) (2,2)
A square (3,3) (4,4)
-
.

Sample Output

A has no intersections
B intersects with S, W, and X
F intersects with W
S intersects with B
W intersects with B and F
X intersects with B

A has no intersections
B has no intersections

Source

CTU Open 2007

Solution:

这是一道线段相交的模板题。

先将所有的几何图形转化成多边形类型,再求多边形是否相交即可。

构造正方形时需要用到的解析几何知识:

  1.  P(x, y) 绕 C(a, b) 逆时针旋转90°得到点 P(a + b - y, b - a + x)。
  2.  P(x, y) 绕 C(a, b) 顺时针旋转90°得到点 P(a - b + y, b + a - x)。

注意读入输出,读入时不能直接用 scanf 来读取。

Code: O(Tn2v2) [216K, 94MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<algorithm>
#define eps 1e-8
#define dmax 1e10
using namespace std;

inline int getint(){
	char ch; int sym = 1, ivar;
	while(!isdigit(ch = getchar())) if(ch == '-') sym = -1;
	ivar = ch - '0';
	while(isdigit(ch = getchar())) ivar = (ivar << 1) + (ivar << 3) + ch - '0';
	return ivar * sym;
}
#define getd() (double)getint()

inline char getNextId(){
	char ch = getchar();
	while(ch < 45) ch = getchar(); // '-' == 45, '.' == 46, ' ' == 32, '\n' == 10
	return ch;
} 

inline int dsgn(const double &x){
	if(fabs(x) <= eps) return 0;
	return (x < 0) ? -1 : 1;
}

struct Polygon;

#define Vector Point
struct Point{
	double x, y;
	
	Point() {}
	Point(double x, double y): x(x), y(y) {}
	
	inline Vector operator - (const Point &p2) const {return Vector(x - p2.x, y - p2.y);}
};

inline double Cross(const Vector &vec1, const Vector &vec2) {return vec1.x * vec2.y - vec1.y * vec2.x;}

inline bool segmentIntersect(const Point &pu, const Point &pv, const Point &qu, const Point &qv){
	if(dsgn(min(pu.x, pv.x) - max(qu.x, qv.x)) <= 0
	&& dsgn(max(pu.x, pv.x) - min(qu.x, qv.x)) >= 0
	&& dsgn(min(pu.y, pv.y) - max(qu.y, qv.y)) <= 0
	&& dsgn(max(pu.y, pv.y) - min(qu.y, qv.y)) >= 0
	&& dsgn(Cross(pv - pu, qu - pu)) * dsgn(Cross(qv - pu, pv - pu)) >= 0
	&& dsgn(Cross(qv - qu, pu - qu)) * dsgn(Cross(pv - qu, qv - qu)) >= 0) return 1;
	return 0;
}

struct Polygon{
	char id;
	Point v[25];
	int vnum;
	
	char interid[30];
	int internum;
	
	inline bool operator < (const Polygon &poly2) const {return id < poly2.id;}
	
	inline void squareConstruct(const Point &p1, const Point &p2){
		Point pmid((p1.x + p2.x) / 2, (p1.y + p2.y) / 2);
		vnum = 4, v[1] = p1, v[3] = p2;
		v[2].x = pmid.x + pmid.y - p1.y, v[2].y = pmid.y - pmid.x + p1.x;
		v[4].x = pmid.x - pmid.y + p1.y, v[4].y = pmid.y + pmid.x - p1.x;
		// The 90 degrees' counter-clockwise rotation of (x, y) around (a, b) is (a + b - y, b - a + x)
		// The 90 degrees' clockwise rotation of (x, y) around (a, b) is (a - b + y, b + a - x)
	}
	
	inline void rectangleConstruct(const Point &p1, const Point &p2, const Point &p3){
		vnum = 4, v[1] = p1, v[2] = p2, v[3] = p3;
		v[4].x = p3.x + p1.x - p2.x, v[4].y = p3.y + p1.y - p2.y;
		// Input guarantees the angle of p1-p2-p3 is right angle
	}
	
	inline void lineConstruct(const Point &p1, const Point &p2) {vnum = 2, v[1] = p1, v[2] = p2;}
	
	inline void triangleConstruct(const Point &p1, const Point &p2, const Point &p3){
		vnum = 3, v[1] = p1, v[2] = p2, v[3] = p3;
		// Input guarantees p1, p2 and p3 not to be co-linear
	}
};

inline bool polygonIntersect(const Polygon &poly1, const Polygon &poly2){
	int prei = poly1.vnum;
	for(register int i = 1; i <= poly1.vnum; i++){
		int prej = poly2.vnum;
		for(register int j = 1; j <= poly2.vnum; j++){
			if(segmentIntersect(poly1.v[i], poly1.v[prei], poly2.v[j], poly2.v[prej]))
				return 1;
			prej = j;
		}
		prei = i;
	}
	return 0;
}

Polygon poly[30];
int polynum;
char tp[15];

int main(){
	char ch = getNextId();
	while(ch != '.'){
		polynum = 0;
		while(ch != '-'){
			poly[++polynum].id = ch;
			scanf("%s", tp);
			switch(tp[0]){
				case 's':{
					double a = getd(), b = getd(), c = getd(), d = getd();
					poly[polynum].squareConstruct(Point(a, b), Point(c, d));
					break;
				}
				case 'r':{
					double a = getd(), b = getd(), c = getd(), d = getd(), e = getd(), f = getd();
					poly[polynum].rectangleConstruct(Point(a, b), Point(c, d), Point(e, f));
					break;
				}
				case 'l':{
					double a = getd(), b = getd(), c = getd(), d = getd();
					poly[polynum].lineConstruct(Point(a, b), Point(c, d));
					break;
				}
				case 't':{
					double a = getd(), b = getd(), c = getd(), d = getd(), e = getd(), f = getd();
					poly[polynum].triangleConstruct(Point(a, b), Point(c, d), Point(e, f));
					break;
				}
				case 'p':{
					poly[polynum].vnum = getint();
					for(register int i = 1; i <= poly[polynum].vnum; i++)
						poly[polynum].v[i].x = getd(), poly[polynum].v[i].y = getd();
					break;
				}
				default: assert(0);
			}
			ch = getNextId();
		}
		sort(poly + 1, poly + polynum + 1);
		for(register int i = 1; i <= polynum; i++) poly[i].internum = 0;
		for(register int i = 1; i <= polynum; i++)
			for(register int j = i + 1; j <= polynum; j++)
				if(polygonIntersect(poly[i], poly[j])){
					poly[i].interid[++poly[i].internum] = poly[j].id;
					poly[j].interid[++poly[j].internum] = poly[i].id;
				}
		for(register int i = 1; i <= polynum; i++){
			if(poly[i].internum == 0) printf("%c has no intersections\n", poly[i].id);
			else{
				printf("%c intersects with", poly[i].id);
				if(poly[i].internum == 1) printf(" %c\n", poly[i].interid[1]);
				else if(poly[i].internum == 2) printf(" %c and %c\n", poly[i].interid[1], poly[i].interid[2]);
				else{
					for(register int j = 1; j < poly[i].internum; j++) printf(" %c,", poly[i].interid[j]);
					printf(" and %c\n", poly[i].interid[poly[i].internum]);
				}
			}
		}
		puts("");
		ch = getNextId();
	}
	return 0;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai