AOJ 0035 - Is it convex?
汚いコードができあがりました.
無駄に外積を使い,三角形内に点があれば凸四角形であると判定します.
#include <iostream> #include <cstdio> class Point{ public: Point(); Point(double _x, double _y); double x, y; }; Point::Point() : x(0), y(0){} Point::Point(double _x, double _y) : x(_x), y(_y){} class Vector{ public: Vector(); Vector(double _x, double _y); Vector(Point p1, Point p2); double x, y; }; Vector::Vector() : x(0), y(0){} Vector::Vector(double _x, double _y) : x(_x), y(_y){} Vector::Vector(Point p1, Point p2) : x(p1.x-p2.x), y(p1.y-p2.y){} class Triangle{ public: Triangle(); Triangle(Point _p1, Point _p2, Point _p3); Point p[3]; }; Triangle::Triangle(Point _p1, Point _p2, Point _p3){ p[0] = _p1, p[1] = _p2, p[2] = _p3; } int extproduct(Vector v1, Vector v2){ return v1.x*v2.y - v1.y*v2.x; } bool triangle_contains(Triangle t, Point p){ int count = 0; for(int i=0;i<3;i++){ Vector a = Vector(t.p[i], t.p[(i+1)%3]), b = Vector(p, t.p[i]); if(extproduct(a, b) > 0)count++; else count--; } return (count%3 != 0); } int main(){ Point ps[4]; while(~scanf("%lf,%lf,%lf,%lf,%lf,%lf,%lf,%lf", &ps[0].x, &ps[0].y, &ps[1].x, &ps[1].y, &ps[2].x, &ps[2].y, &ps[3].x, &ps[3].y)){ int i = 0; for(;i<4;i++){ if(triangle_contains(Triangle(ps[(i+1)%4], ps[(i+2)%4], ps[(i+3)%4]), ps[i]) == false)break; } if(i == 4)puts("YES"); else puts("NO"); } }