TopCoder SRM 641 DIV2 Level2
概要
xy平面上にいくつかの点が与えられる。
この点の中から3つ選んで三角形を作った時、
原点が三角形の内部に含まれるような組み合わせが
何通りあるか求めよ。
解法
三角形がある点を内包するとき、
ベクトルの外積が同じ向きを向く。
この性質を利用する。
コード
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <climits> #include <algorithm> #include <cmath> #include <cstdlib> #include <stack> #include <queue> #include <string> #include <map> #include <set> #include <sstream> #include <functional> #include <ctime> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define CLEAR(d) memset((d), 0, (sizeof((d)))) #define ALL(c) (c).begin(), (c).end() #define ABS(x) ((x < 0) ? -(x) : (x)) #define SORT(x) sort((x).begin(), (x).end()) #define RSORT(x) sort((x).begin(), (x).end(), greater<int>() ) #define SIZE(a) ((int)((a).size())) #define MOD 1000000007 #define EPS 1e-7 #define PI (acos(-1)) #define INF 10000000 struct edge { int to; int cost; }; //=================================================== class Point { public: double x, y; Point() : x(0), y(0) {} Point(double x, double y) : x(x), y(y) {} Point operator + (Point p) { return Point(add(x, p.x), add(y, p.y)); } Point operator - (Point p) { return Point(add(x, -p.x), add(y, -p.y)); } Point operator * (double d) { return Point(x * d, y * d); } bool operator < (Point p) { return x == p.x ? y < p.y : x < p.x; } double add(double a, double b) { if (abs(a + b) < EPS * (abs(a) + abs(b))) return 0; return a + b; } double dot(Point p) { return add(x * p.x, y * p.y); } double det(Point p) { return add(x * p.y, -y * p.x); } }; bool innerCheck(Point p1, Point p2, Point p3) { Point p0 = Point(0.0, 0.0); double c1 = (p3 - p1).det(p1 - p0) + 0; double c2 = (p2 - p3).det(p3 - p0) + 0; double c3 = (p1 - p2).det(p2 - p0) + 0; if ((c1 > 0 && c2 > 0 && c3 > 0) || (c1 < 0 && c2 < 0 && c3 < 0)) { return true; } return false; } class TrianglesContainOriginEasy { public : int count(vector <int> x, vector <int> y) { int ans = 0; int size = x.size(); vector<Point> vects; for (int i = 0; i < size; i++) { vects.push_back(Point((double)x[i], (double)y[i])); } for (int i = 0; i < size-2; i++) { for (int j = i+1; j < size-1; j++) { for (int k = j+1; k < size; k++) { if (innerCheck(vects[i], vects[j], vects[k])) { ans++; } } } } return ans; } };