今天下午寝室没网了,打电话人家说要修,等两天吧= =。。。下午ZOJ月赛都没做。。
听了这个后,我决定开通移动的WLAN了。。。10RMB 40个小时。。。
开通前没网的时候找了这个题。。。输入输出真麻烦。。。不过还好过程理清后比较简单。
输出序列我用set了,可以去重哈。
#include <set> #include <map> #include <queue> #include <stack> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <iostream> #include <limits.h> #include <string.h> #include <string> #include <algorithm> #define MID(x,y) ( ( x + y ) >> 1 ) #define L(x) ( x << 1 ) #define R(x) ( x << 1 | 1 ) #define FOR(i,s,t) for(int i=s; i<t; i++) #define BUG puts("here!!!") using namespace std; const int MAX = 30; const double eps = 1e-6; bool dy(double x,double y) { return x > y + eps;} // x > y bool xy(double x,double y) { return x < y - eps;} // x < y bool dyd(double x,double y) { return x > y - eps;} // x >= y bool xyd(double x,double y) { return x < y + eps;} // x <= y bool dd(double x,double y) { return fabs( x - y ) < eps;} // x == y struct point{ double x,y; void get() { scanf("%lf%lf", &x, &y);} point P(double x,double y) { point c; c.x = x; c.y = y; return c; } }; point operator-(point a,point b){ point c; return c.P(a.x - b.x, a.y - b.y);} point operator+(point a,point b){ point c; return c.P(a.x + b.x, a.y + b.y);} struct polygon{ point c[30]; int n;}; polygon p[MAX]; bool alp[MAX]; point Whirl(double cosl, double sinl, point a, point b) { b.x -= a.x; b.y -= a.y; point c; c.x = b.x * cosl - b.y * sinl + a.x; c.y = b.x * sinl + b.y * cosl + a.y; return c; } void input_s(char *s, int ind) { int n; if( strcmp(s, "square") == 0 ) { double x1, y1, x2, y2; scanf("%s", s); sscanf(s, "(%lf,%lf)", &p[ind].c[0].x, &p[ind].c[0].y); scanf("%s", s); sscanf(s, "(%lf,%lf)", &p[ind].c[2].x, &p[ind].c[2].y); point mid; mid.x = (p[ind].c[0].x + p[ind].c[2].x)/2; mid.y = (p[ind].c[0].y + p[ind].c[2].y)/2; p[ind].c[1] = Whirl(0, 1, mid, p[ind].c[0]); p[ind].c[3] = Whirl(0, 1, mid, p[ind].c[2]); p[ind].c[4] = p[ind].c[0]; p[ind].n = 4; } if( strcmp(s, "rectangle") == 0 ) { FOR(i, 0, 3) { scanf("%s", s); sscanf(s, "(%lf,%lf)", &p[ind].c[i].x, &p[ind].c[i].y); } point c = p[ind].c[2] - p[ind].c[1]; p[ind].c[3] = p[ind].c[0] + c; p[ind].c[4] = p[ind].c[0]; p[ind].n = 4; } if( strcmp(s, "line") == 0 ) { FOR(i, 0, 2) { scanf("%s", s); sscanf(s, "(%lf,%lf)", &p[ind].c[i].x, &p[ind].c[i].y); } p[ind].n = 1; } if( strcmp(s, "triangle") == 0 ) { FOR(i, 0, 3) { scanf("%s", s); sscanf(s, "(%lf,%lf)", &p[ind].c[i].x, &p[ind].c[i].y); } p[ind].c[3] = p[ind].c[0]; p[ind].n = 3; } if( strcmp(s, "polygon") == 0 ) { scanf("%d", &n); FOR(i, 0, n) { scanf("%s", s); sscanf(s, "(%lf,%lf)", &p[ind].c[i].x, &p[ind].c[i].y); } p[ind].c[n] = p[ind].c[0]; p[ind].n = n; } } double crossProduct(point a,point b,point c)//向量 ac 在 ab 的方向 { return (c.x - a.x)*(b.y - a.y) - (b.x - a.x)*(c.y - a.y); } bool onSegment(point a, point b, point c) { if( dd(crossProduct(a,b,c),0.0) && dyd(c.x,min(a.x,b.x)) && xyd(c.x,max(a.x,b.x)) && dyd(c.y,min(a.y,b.y)) && xyd(c.y,max(a.y,b.y)) ) return true; return false; } bool s2s_inst(point p1,point p2, point p3, point p4) { double d1 = crossProduct(p3,p4,p1); double d2 = crossProduct(p3,p4,p2); double d3 = crossProduct(p1,p2,p3); double d4 = crossProduct(p1,p2,p4); if( xy(d1 * d2,0.0) && xy(d3 * d4,0.0) ) return true; if( dd(d1,0.0) && onSegment(p3,p4,p1) || dd(d2,0.0) && onSegment(p3,p4,p2) || dd(d3,0.0) && onSegment(p1,p2,p3) || dd(d4,0.0) && onSegment(p1,p2,p4) ) return true; return false; } set<int> myset; set<int>::iterator it; bool ins[MAX]; void inst(int ind, point a,point b) { FOR(i, 0, MAX) { if( i == ind ) continue; if( alp[i] == 0 ) continue; if( ins[i] == true ) continue; FOR(k, 0, p[i].n) if( s2s_inst(a, b, p[i].c[k], p[i].c[k+1]) ) { ins[i] == true; myset.insert(i); break; } } } void solve() { FOR(i, 0, MAX) { if( alp[i] == 0 ) continue; myset.clear(); memset(ins, false, sizeof(ins)); FOR(k, 0, p[i].n) inst(i, p[i].c[k], p[i].c[k+1]); if( myset.size() == 0 ) printf("%c has no intersections\n",i+'A'); if( myset.size() == 1 ) printf("%c intersects with %c\n", i+'A',(*myset.begin())+'A'); if( myset.size() == 2 ) { it = myset.begin(); int a = *it; it++; int b = *it; printf("%c intersects with %c and %c\n",i+'A', a+'A', b+'A'); } if( myset.size() >= 3 ) { printf("%c intersects with ", i+'A'); int cnt; for(it=myset.begin(), cnt = 0; cnt < myset.size()-1; it++, cnt++) printf("%c, ",*it+'A'); printf("and %c\n",*it+'A'); } } } int main() { char s[15]; int ind = 0; while( ~scanf("%s", s) ) { memset(alp, 0, sizeof(alp)); if( s[0] == '.' ) break; if( s[0] == '-' ) continue; ind = s[0]-'A'; alp[ind] = 1; scanf("%s", s); input_s(s, ind); while( scanf("%s", s) ) { if( s[0] == '-' ) break; ind = s[0]-'A'; alp[ind] = 1; scanf("%s", s); input_s(s, ind); } solve(); printf("\n"); } return 0; }