TopCoder SRM 641 DIV2 Level2

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13547

概要

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;
    }
};