Submission #1303207

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;

#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b)) < EPS)
static const int COUNTER_CLOCKWISE = 1;
static const int CLOCKWISE = -1;
static const int ONLINE_BACK = 2;
static const int ONLINE_FRONT = -2;
static const int ON_SEGMENT = 0;

struct Point {
	double x, y;

	Point(double x = 0, double y = 0) :x(x), y(y) {}

	Point operator + (Point p) { return Point(x + p.x, y + p.y); }
	Point operator - (Point p) { return Point(x - p.x, y - p.y); }
	Point operator * (Point p) { return Point(x * p.x, y * p.y); }
	Point operator / (Point p) { return Point(x / p.x, y / p.y); }

	double abs() { return sqrt(norm()); }
	double norm() { return x*x + y*y; }

	bool operator < (const Point &p)const {
		return x != p.x ? x < p.x : y < p.y;
	}
	bool operator ==(const Point &p)const {
		return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
	}
};
typedef Point Vector;
struct Segment { Point p1, p2; };

double dot(Vector a, Vector b) {
	return a.x * b.x - a.y*b.y;
}
double cross(Vector a, Vector b) {
	return a.x*b.y - a.y*b.x;
}
int ccw(Point p0, Point p1, Point p2) {
	Vector a = p1 - p0;
	Vector b = p2 - p0;
	if (cross(a, b) > EPS)return COUNTER_CLOCKWISE;
	if (cross(a, b) < -EPS)return CLOCKWISE;
	if (dot(a, b) < -EPS)return ONLINE_BACK;
	if (a.norm() < b.norm())return ONLINE_FRONT;

	return ON_SEGMENT;
}
bool intersect(Point p1, Point p2, Point p3, Point p4) {
	return(ccw(p1, p2, p3)*ccw(p1, p2, p4) <= 0 && ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0);
}
bool intersect(Segment s1,Segment s2) {
	return intersect(s1.p1, s1.p2, s2.p1, s2.p2);
}

int main()
{
	Segment s;
	cin >> s.p1.x >> s.p1.y >> s.p2.x >> s.p2.y;
	int N; cin >> N;
	vector<Point>Ps(N);
	for (int i = 0; i < N; i++) {
		double x, y; cin >> x >> y;
		Ps[i] = Point(x, y);
	}

	int cnt = 0;
	for (int i = 1; i <=N; i++) {
		int i2 = i%N;
		int i1 = i - 1;

		Segment s2;
		s2.p1 = Ps[i1];
		s2.p2 = Ps[i2];
		cnt += intersect(s,s2);
	}

	cout << 1 + cnt/2 << endl;

    return 0;
}

Submission Info

Judge Result