人魚の魔女 (AOJ 2316)
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2316
問題
略
解法
やるだけ。鋭く凹んでる場合に今の軸の反対側の頂点が次の軸になることがあるので注意。
#include <stdio.h> #include <string.h> #include <algorithm> #include <iostream> #include <math.h> #include <assert.h> #include <vector> using namespace std; typedef long long ll; typedef unsigned int uint; typedef unsigned long long ull; static const double EPS = 1e-7; static const double PI = acos(-1.0); #define REP(i, n) for (int i = 0; i < (int)(n); i++) #define FOR(i, s, n) for (int i = (s); i < (int)(n); i++) #define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++) #define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++) #define MEMSET(v, h) memset((v), h, sizeof(v)) #include <complex> typedef complex<double> Point; struct Line : public vector<Point> { Line() {;} Line(Point a, Point b) { push_back(a); push_back(b); } }; struct Circle { Point p; double r; Circle() {;} Circle(Point p, double r) : p(p), r(r) {;} }; namespace std { bool operator<(const Point &lhs, const Point &rhs) { return lhs.real() == rhs.real() ? lhs.imag() < rhs.imag() : lhs.real() < rhs.real(); } } //--------------------- int zoom = 1; void chcolor(int r, int g, int b) { fprintf(stderr, "c.strokeStyle = 'rgb(%d, %d, %d)';\n", r, g, b); } void drawline(Line l) { fprintf(stderr, "line(%d, %d, %d, %d)\n", (int)(zoom*l[0].real()), 1980-(int)(zoom*l[0].imag()), (int)(zoom*l[1].real()), 1980-(int)(zoom*l[1].imag())); } //----------------------------- inline double cross(const Point &a, const Point &b) { return imag(conj(a) * b); } inline double dot(const Point &a, const Point &b) { return real(conj(a) * b); } Point projection(const Line &l, const Point &p) { double t = dot(p - l[0], l[0] - l[1]) / norm(l[0] - l[1]); return l[0] + t * (l[0] - l[1]); } bool intersectSP(const Line &s, const Point &p) { return abs(s[0] - p) + abs(s[1] - p) - abs(s[1] - s[0]) < EPS; } vector<Point> crosspointLC(const Line &l, const Circle &c) { vector<Point> ret; Point center = projection(l, c.p); double d = abs(center - c.p); double t = sqrt(c.r * c.r - d * d); if (isnan(t)) { return ret; } Point vect = (l[1] - l[0]); vect /= abs(vect); ret.push_back(center - vect * t); if (t > EPS) { ret.push_back(center + vect * t); } return ret; } vector<Point> crosspointSC(const Line &s, const Circle &c) { vector<Point> ret; vector<Point> nret = crosspointLC(s, c); for (int i = 0; i < (int)nret.size(); i++) { if (intersectSP(s, nret[i])) { ret.push_back(nret[i]); } } return ret; } //========================== const double sq2 = sqrt(2.0); struct Square { Point axis; Point vect; int color; void Rotate(Point p) { vect = axis - p; axis = p; color++; assert(abs(abs(vect) - 1.0) <= EPS); } void SpecialRotate(Point p) { vect = ((axis - p) / sq2) * Point(cos(PI / 4.0), sin(PI / 4.0)); axis = p; color += 2; assert(abs(abs(vect) - 1.0) <= EPS); } }; int n, sx, gx; Square square; Line segments[100010]; inline bool CompareRadian(double lhsR, bool lhsS, double rhsR, bool rhsS) { if (lhsS) { lhsR += PI / 4.0; } if (rhsS) { rhsR += PI / 4.0; } return lhsR - rhsR < -EPS; } pair<Point, double> FirstPoint(const vector<Point> &candidate, int index) { double minRadian = 1e+100; bool minSecond = false; Point firstPoint(-1e+100, -1e+100); FORIT(it, candidate) { if (it->real() < square.axis.real()) { continue; } Point v = *it - square.axis; bool second = abs(v) - 1.0 < EPS ? 0 : 1; v /= abs(v); double radian = acos(dot(square.vect, v)); if (isnan(radian)) { radian = PI; } //cout << *it << " " << v << " " << radian << endl; if (CompareRadian(radian, second, minRadian, minSecond)) { minSecond = second; minRadian = radian; firstPoint = *it; } } assert(minRadian != 1e+100); return make_pair(firstPoint, minRadian); } int main(int argc, char *argv[]) { if (argc >= 2) { zoom = atoi(argv[1]); } while (scanf("%d %d %d", &n, &sx, &gx) > 0) { { // input int px = 0; int py = 0; int v = scanf("%d %d", &px, &py); assert(v == 2); REP(i, n - 1) { int nx, ny; int v = scanf("%d %d", &nx, &ny); assert(v == 2); segments[i] = Line(Point(px, py), Point(nx, ny)); px = nx; py = ny; } segments[n - 1] = Line(segments[n - 2][1], segments[n - 2][1] * 2.0 - segments[n - 2][0]); segments[n] = Line(segments[n - 1][1], segments[n - 1][1] * 2.0 - segments[n - 1][0]); } // init square.vect = segments[0][0] - segments[0][1]; square.vect /= abs(square.vect); square.axis = -square.vect * (1.0 + (sx - segments[0][0].real()) / -square.vect.real()) + segments[0][0]; square.color = 0; int index = 0; #ifdef visualize chcolor(0, 0, 0); REP(i, n - 1) { drawline(segments[i]); } #endif // process while (true) { #ifdef visualize { int co = square.color % 4; if (co == 0) { chcolor(250, 10, 10); } else if (co == 1) { chcolor(0, 180, 0); } else if (co == 2) { chcolor(0, 0, 200); } else if (co == 3) { chcolor(100, 100, 100); } drawline(Line(square.axis, square.axis + square.vect)); drawline(Line(square.axis, square.axis + square.vect * Point(0, -1))); drawline(Line(square.axis + square.vect * Point(1, -1), square.axis + square.vect)); drawline(Line(square.axis + square.vect * Point(1, -1), square.axis + square.vect * Point(0, -1))); } #endif if (square.axis.real() - gx >= -EPS) { break; } Circle c1(square.axis, 1.0); Circle c2(square.axis, sq2);; vector<Point> candidate[5]; candidate[0] = crosspointSC(segments[index], c1); candidate[1] = crosspointSC(segments[index + 1], c1); candidate[2] = crosspointSC(segments[index + 2], c1); candidate[3] = crosspointSC(segments[index + 1], c2); candidate[4] = crosspointSC(segments[index + 2], c2); vector<Point> candidates; REP(i, 5) FORIT(it, candidate[i]) { candidates.push_back(*it); } pair<Point, double> rot = FirstPoint(candidates, index); //cout << square.vect << endl; //cout << rot.first << " " << rot.second << " " << abs(rot.first - square.axis) << endl; if (abs(rot.first - square.axis) - 1.0 < EPS) { square.Rotate(rot.first); } else { square.SpecialRotate(rot.first); } if (!intersectSP(segments[index], rot.first)) { index++; } } const char *ans[4] = { "Red", "Green", "Blue", "White" }; printf("%s\n", ans[square.color % 4]); //cout << square.color << endl;; } }
