AOJ0153 Triangle and Circle
解法
容易に定まる条件を持つものから決定していく。
円の中心が三角形の内側にあるかどうか調べる必要があるが、これはCCWするかそれに値するような外積の符号を見る式を書けばよい。内積で角度出してやろうとしたらうまく行かなかった。単純なミスなのか、本当にうまくいかないのかは今後調べる必要がある。
今回の contains 関数は Spagetti Source とほぼ同じ。
#include <iostream> #include <algorithm> #include <complex> #include <vector> #include <cmath> using namespace std; #define F first #define S second #define X real() #define Y imag() #define EPS (1e-7) typedef complex<double> Point; typedef vector<Point> Polygon; typedef pair<double, Point> Circle; bool isPointInCircle(const Point& p, const Circle& c) { if(abs(p-c.S) < abs(c.F) + EPS) return true; return false; } double dot(const Point& a, const Point& b) { return a.X*b.X+a.Y*b.Y; } double cross(const Point& a, const Point& b) { return a.X*b.Y-a.Y*b.X; } typedef pair<Point, Point> Segment; typedef Segment Line; double distanceLP(Line l, Point p) { return abs(cross(l.S-l.F, p-l.F)) / abs(l.S-l.F); } double distanceSP(Segment s, Point p) { Point a = s.F, b = s.S; if(dot(b-a, p-a) < EPS) return abs(p-a); if(dot(a-b, p-b) < EPS) return abs(p-b); return distanceLP(s, p); } enum struct ECont { OUT, ON, IN }; ECont contains(const Polygon& poly, const Point& p) { bool in = 0; for(int i=0; i<poly.size(); i++) { Point a = poly[i] - p, b = poly[(i+1)%poly.size()] - p; if(a.imag() > b.imag()) swap(a, b); if(a.imag() <= 0 && 0 < b.imag()) { if(cross(a, b) < 0) in = !in; } if(cross(a, b) == 0 && dot(a, b) <= 0) return ECont::ON; } return in ? ECont::IN : ECont::OUT; } int main() { while(1) { Polygon points(3); Circle circle; for(int i=0; i<3; i++) { double x, y; cin >> x >> y; if(x == 0) return 0; points[i] = Point(x, y); } { double x, y; cin >> x >> y; circle.S = Point(x, y); cin >> circle.F; } bool ok = 1; for(int i=0; i<3; i++) { ok &= isPointInCircle(points[i], circle); } if(ok) { cout << 'b' << endl; continue; } int uncross = 0; for(int i=0; i<3; i++) { Segment seg = make_pair(points[(i+1)%3], points[i]); uncross += circle.F < distanceSP(seg, circle.S) + EPS; } if(uncross == 3) { int flg = 0; for(int i=0; i<3; i++) { if(contains(points, circle.S) == ECont::IN) { flg ++; } } if(flg == 3) { cout << 'a' << endl; continue; } } int cross = 0; for(int i=0; i<3; i++) { Segment seg = make_pair(points[(i+1)%3], points[i]); cross += distanceSP(seg, circle.S) <= circle.F + EPS; } if(cross > 0) cout << 'c' << endl; else cout << 'd' << endl; } return 0; }