This is a BIG set of Computational Geometry related notes.

Bouvardia的计算几何入门大合集.

Table of Contents

  1. Overview
  2. Basic Element
    1. Point
    2. Vector
    3. Line
    4. Circle
    5. Polygon
  • Basic Option
    1. Judging Direction Relationship between 2 Vectors
    2. Getting Perpendicular Vector (Right Hand)
    3. Getting The Distance From Point to Line
    4. 快速排斥实验与跨立实验
    5. Judging Direction Relationship between Point and Line
    6. Calculating 2 Lines’ intersection position
    7. Calculating the Area of Polygon
  • Half-Plane Intersection(HPI)
  • Rotating Calipers
    1. BOI2011 2circles
      1. Description
      2. Solution
      3. Code
  • Minimum Circle-Coverage Problem
    1. BZOJ 1336&1337
  • Convex Hull
    1. BZOJ 1007
      1. Description
      2. Solution
    2. 51Nod 1543
      1. Description
      2. Solution
  • Practical Usage
    1. CodeM 2018 Final F
      1. Description
      2. Solution

    • Overview

    NAN.

    Basic Element

    Point

    定义在二维平面上的点.

    Vector

    基于坐标表示法的向量, 支持向量运算.

    Line

    基于点+向量表示法的直线, 在模板中右侧定义为半平面.

    Circle

    定义了坐标(点) 和半径的圆.

    Polygon

    定义了顶点个数和顶点集合的多边形.

    Basic Option

    Judging Direction Relationship between 2 Vectors

    叉积$\overrightarrow{a} \times \overrightarrow{b} \le 0$, 则 $a$ 在 $b$ 左侧.

    Getting Perpendicular Vector (Right Hand)

    $(x, y) \rightarrow (y, -x)$

    Getting The Distance From Point to Line

    面积转换, 定义直线 $l$ , 有$d = \frac{|( P - l.P ) \times l.v|}{|l.v|} $

    快速排斥实验与跨立实验

    判断两线段覆盖矩形是否交, 叉积判断两点是否分立.

    Judging Direction Relationship between Point and Line

    定义向量$a = p - l.p$, 判断向量关系.

    Calculating 2 Lines’ intersection position

    对于直线$a, b$: $Point P = b.p + b.v * (a.v \times (a.p - b.p)) / (a.v \times b.v)$ , 根据向量叉积面积放缩, 负值可抵消.

    Calculating the Area of Polygon

    对于每两个点计算叉积面积并累加, 多余部分可抵消. 叉积计算的是平行四边形面积, 记得$\times 0.5$的说.

    Bouvardia有话要说. 对于某些基于整点的多边形面积问题, 或有关问题, 可以想到叉积法求出的面积$\times 2$总是整数, 从而设计状态.

    *To Be Continue...*

    Half-Plane Intersection(HPI)

    话说Bouvardia做题的时候手贱写成了NOI来的……

    给出二维平面上的若干个半平面, 或者线性规划关系, 通常以直线方向向量向右为可行域. 求半平面的交集, 也即可行域. 问题可能有凸包顶点, 可行域面积等.

    常用的$O(nlogn)$算法是, 对所有直线按极角排序, 维护一个双端队列. 每次插入时, 判断队尾&队头两线交点与新线是否合法, 弹队列, 新线插入队尾.

    需要注意的是, 若队列中只有一个元素, 而仍与新线不合法, 则无解.

    做完后我们得到了一个凸包, 利用叉积求面积, 或者做一些其他操作就好了.

    放一个模板, 这是POJ 2451.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    #include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cstdio>
    #include <cstring>

    using namespace std;

    const int inf = 10000;
    const int maxn = 20005;

    namespace geometric_lib
    {
    	using std::sort;
    	//basic geometry element
    	typedef long double ldb;
    	const ldb eps = 1e-10;
    	struct Vector
    	{
    		ldb x, y;
    		Vector(ldb x_ = 0.0, ldb y_ = 0.0):x(x_), y(y_){}
    		Vector operator + (Vector rhs)
    		{
    			return Vector(x + rhs.x, y + rhs.y);
    		}
    		Vector operator - (Vector rhs)
    		{
    			return Vector(x - rhs.x, y - rhs.y);
    		}
    		friend Vector operator * (Vector lhs, ldb rhs)
    		{
    			return Vector(rhs * lhs.x, rhs * lhs.y);
    		}
    		ldb operator * (Vector rhs)
    		{
    			return x * rhs.x + y * rhs.y;
    		}
    		ldb operator ^ (Vector rhs)
    		{
    			return x * rhs.y - y * rhs.x;
    		}
    	};
    	typedef Vector Point;
    	//public functions:
    	int DCMP(ldb x)
    	{
    		return (x < -eps) ? -1 : (x > eps);
    	}
    	struct Line
    	{
    		Point P;
    		Point V;
    		ldb Ang;
    		Line(Point P_ = Point(), Point V_ = Point()):P(P_), V(V_)
    		{Ang = atan2(V_.y, V_.x);}//}
    		/*inline void getAngle()
    		{
    			Ang = atan2(V.y, V.x);
    		}*/
    		bool operator < (const Line &rhs) const
    		{
    			//getAngle(); rhs.getAngle();
    			return Ang < rhs.Ang;
    		}
    	};
    	
    	// half-plane intersection:
    	int n;
    	Point pts[maxn];
    	Line pln[maxn], q[maxn];
    	bool LEGAL(Point P_, Line L_)
    	{
    		return DCMP((P_ - L_.P)^L_.V) >= 0;
    	}
    	Point intersection(Line a, Line b)
    	{
    		return b.P + b.V*((a.V ^ (a.P - b.P))/(a.V ^ b.V));
    	}
    	ldb HPI() //right hand HPI
    	{
    		pln[++n] = Line(Point(0, 0), Point(0, 1));
    		pln[++n] = Line(Point(0, inf), Point(1, 0));
    		pln[++n] = Line(Point(inf, inf), Point(0, -1));
    		pln[++n] = Line(Point(inf, 0), Point(-1, 0));
    		sort(pln + 1, pln + 1 + n);
    		int tot = 0;
    		//unique:
    		for(int i = 1; i <= n; ++i)
    		{
    			if(!tot) pln[++tot] = pln[i];
    			else if(DCMP(pln[tot].Ang - pln[i].Ang) != 0) pln[++tot] = pln[i];
    			else if(LEGAL(pln[i].P, pln[tot])) pln[tot] = pln[i];
    		}
    		n = tot; int hd = 1, tl = 2;
    		q[1] = pln[1]; q[2] = pln[2];
    		for(int i = 3; i <= n; ++i)
    		{
    			while(hd != tl && !LEGAL(intersection(q[tl], q[tl - 1]), pln[i])) --tl;
    			while(hd != tl && !LEGAL(intersection(q[hd], q[hd + 1]), pln[i])) ++hd;
    			if(hd == tl && DCMP(q[hd].V ^ pln[i].V) <= 0) return 0;// No Solution
    			q[++tl] = pln[i];
    		}
    		while(hd != tl && !LEGAL(intersection(q[tl], q[tl - 1]), q[hd])) --tl;
    		int len = tl - hd + 1;
    		for(int i = 1; i < len; ++i) pts[i] = intersection(q[hd + i], q[hd + i - 1]);
    		pts[0] = pts[len] = intersection(q[tl], q[hd]);
    		ldb area = 0.0;
    		for(int i = 0; i < len; ++i) area += pts[i] ^ pts[i + 1];
    		return area * 0.5;
    	}
    	void HPI_main()
    	{
    		while(scanf("%d", &n) != EOF)
    		{
    			ldb x1, x2, y1, y2;
    			for(int i = 1; i <= n; ++i)
    			{
    				scanf("%Lf%Lf%Lf%Lf", &x1, &y1, &x2, &y2);
    				Point u(x1, y1), v(x2, y2);
    				pln[i] = Line(v, u - v);
    			}
    			printf("%.1Lf\n", HPI());
    		}
    	}
    };

    int main()
    {
    	geometric_lib::HPI_main();
    	return 0;
    }

    似乎有点过度封装了呢……不过Bouvardia还打算继续加入功能的说.

    Rotating Calipers

    BOI2011 2circles

    Description

    我们将会研究一个有N 个顶点的凸多边形。我们希望找到一个最大的半径R，使得两个半径为R 的圆能完全地放置在给出的多边形内，并没有重叠。

    Solution

    最大化不太好做的说. 所以要考虑二分答案.

    那么如何验证呢?

    把多边形向里推, 如果推完后多边形内仍存在一条$\ge 2mid$的线段, 则合法.

    证明:

    所以做法就是二分答案+半平面交+旋转卡壳啦.

    向量的 Perpendicular, Adjust 以及直线的 Translate 操作已经集成进来啦.

    Code

    只有核心代码~

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    //in namespace geometric_lib:
    	
    	ldb norm(Point a)
    	{
    		return sqrt(a*a);
    	}
    	ldb dist(Point a, Point b)
    	{
    		return norm(a - b);
    	}
    	Point perpendicular(Point a)
    	{
    		return Point(a.y, -a.x);
    	}
    	Point adjust(Point a, ldb d)
    	{
    		return Point(a*(d/norm(a)));
    	}

    	Line translate(Line a, ldb d)//d: <0 left, >0 right
    	{
    		return Line(a.P + adjust(perpendicular(a.V), d), a.V);
    	}
    	
    	ldb checking_bound;
    	
    	bool rotating_caliper(Point *ps, int ps_count)
    	{
    		ldb mx = 0, x; int pos;
    		for(int i = 2; i <= ps_count; ++i)
    		{
    			x = dist(ps[1], ps[i]);
    			if(x > mx) mx = x, pos = i;
    		}
    		//plug-in: run faster
    		if(mx >= checking_bound) return 1;
    		for(int i = 2; i <= ps_count; ++i)
    		{
    			mx = dist(ps[pos], ps[i]);
    			while(1)
    			{
    				x = dist(ps[pos % ps_count + 1], ps[i]);
    				if(x > mx) mx = x, pos = pos % ps_count +1;
    				else break;
    			}
    			if(mx >= checking_bound) return 1;
    		}
    		return 0;
    	}
    	//addition
    	#define MAX_N 50001
    	Point a[MAX_N];
    	Line tpln[MAX_N];

    	bool chk(ldb mid)
    	{
    		//set checking_bound
    		checking_bound = mid * 2.0;
    		for(int i = 1; i <= n; ++i) pln[i] = translate(tpln[i], mid);
    		//int pcnt = HPI();
    		return rotating_caliper(pts, HPI());
    	}
    	void solution_main()
    	{
    		scanf("%d", &n);
    		for(int i = 1; i <= n; ++i) scanf("%Lf%Lf", &a[i].x, &a[i].y);
    		for(int i = 1; i <= n; ++i)
    		{
    			int j = i % n + 1;
    			tpln[i] = Line(a[j], a[i] - a[j]);
    		}	
    		ldb l = 0.0, r = 20000000.0;
    		while(l < r)
    		{
    			ldb mid = (l + r + 0.001) * 0.5;
    			if(chk(mid)) l = mid;
    			else r = mid - 0.001;
    		}
    		printf("%.3Lf\n", l);
    	}
    	#undef MAX_N

    Minimum Circle-Coverage Problem

    BZOJ 1336&1337

    一种可以在$O(n)$时间内求出覆盖所有点的最小圆的算法.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    #include <ctime>
    #include <cstdlib>

    namespace geometric_lib
    {
    	const double eps = 1e-10;
    	const int maxn = 1e+5 + 5;
    	using std::srand;
    	using std::time;
    	using std::random_shuffle;
    	struct Vector
    	{
    		double x, y;
    		Vector(double x_ = 0.0, double y_ = 0.0):x(x_), y(y_){}
    		Vector operator + (Vector rhs)
    		{
    			return Vector(x + rhs.x, y + rhs.y);
    		}
    		Vector operator - (Vector rhs)
    		{
    			return Vector(x - rhs.x, y - rhs.y);
    		}
    		friend Vector operator * (Vector lhs, double rhs)
    		{
    			return Vector(rhs * lhs.x, rhs * lhs.y);
    		}
    		double operator * (Vector rhs)
    		{
    			return x * rhs.x + y * rhs.y;
    		}
    		double operator ^ (Vector rhs)
    		{
    			return x * rhs.y - y * rhs.x;
    		}
    	};
    	typedef Vector Point;
    	double norm(Point a)
    	{
    		return sqrt(a*a);
    	}
    	struct Circle
    	{
    		Point c;
    		double r;
    		Circle(Point P_ = Point(), double r_ = 0.0):c(P_), r(r_){} 
    	};
    	

    	//Minimal circle-cover
    	int N;
    	Point pts[maxn];
    	Circle o;
    	void circum(Point p, Point q, Point s)
    	{
    		double a = 2 * (q.x - p.x), b = 2 * (q.y - p.y);
    		double c = q.x * q.x + q.y * q.y - p.x * p.x - p.y * p.y;
    		double d = 2 * (s.x - p.x), e = 2 * (s.y - p.y);
    		double f = s.x * s.x + s.y * s.y - p.x * p.x - p.y * p.y;
    		o.c.x = (b * f - e * c) / (b * d - e * a);
    		o.c.y = (d * c - a * f) / (b * d - e * a);
    		o.r = norm(p - o.c);
    	}
    	void cover_main()
    	{
    		srand(time(NULL));
    		scanf("%d", &N);
    		for(int i = 1; i <= N; ++i) scanf("%lf%lf", &pts[i].x, &pts[i].y);
    		random_shuffle(pts + 1, pts + 1 + N);
    		o.c = pts[1]; o.r = 0.0;
    		for(int i = 2; i <= N; ++i)
    		{
    			if(norm(pts[i] - o.c) > o.r + eps)
    			{
    				o.c = pts[i]; o.r = 0.0;
    				for(int j = 1; j <= i - 1; ++j)
    				{
    					if(norm(pts[j] - o.c) > o.r + eps)
    					{
    						o.c.x = (pts[j].x + pts[i].x) * 0.5;
    						o.c.y = (pts[j].y + pts[i].y) * 0.5;
    						o.r = norm(o.c - pts[j]);
    						for(int k = 1; k <= j - 1; ++k)
    							if(norm(pts[k] - o.c) > o.r + eps)
    								circum(pts[i], pts[j], pts[k]);
    					}
    				}
    			}
    		}
    		printf("%.3lf\n", o.r);
    	}
    };

    int main()
    {
    	geometric_lib::cover_main();
    	return 0;
    }

    Convex Hull

    BZOJ 1007

    Description

    站在无限高处向下看，计算可见直线的编号。

    Solution

    这就是一个维护凸壳的板题啦。首先对直线按极角/斜率排序，单调栈(也可能有其他数据结构的说，建立在直线加入的顺序上)维护凸壳，每次加入新直线，若交点更靠左则弹栈。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>

    using namespace std;

    const int maxn = 50005;
    const double eps = 1e-8;

    struct Line
    {
    	double k, b;
    	int id;
    	bool operator < (const Line &rhs) const
    	{
    		return k == rhs.k ? b < rhs.b : k < rhs.k;
    	}
    }l[maxn];
    int n, stk[maxn], top, v[maxn];

    double intersection(Line p, Line q)
    {
    	return (q.b - p.b) / (p.k - q.k);
    }

    int main()
    {
    	scanf("%d", &n);
    	for(int i = 1; i <= n; ++i) 
    		scanf("%lf%lf", &l[i].k, &l[i].b), l[i].id = i;
    	sort(l + 1, l + 1 + n);
    	for(int i = 1; i <= n; ++i)
    	{
    		if(l[i].k == l[i + 1].k && i != n) continue;
    		while(top > 1 && 
    			intersection(l[i], l[stk[top]]) - intersection(l[stk[top]], l[stk[top - 1]]) <= eps) top--;
    		stk[++top] = i;
    	}
    	for(int i = 1; i <= top; ++i) v[i] = l[stk[i]].id;
    	sort(v + 1, v + 1 + top);
    	for(int i = 1; i <= top; ++i) printf("%d ", v[i]);
    	return 0;
    }

    51Nod 1543

    Description

    铁人两项包含两个部分：游泳和跑步。选手们先跑R米，然后再游S米。胜者是用时最短的人（如果多个人用时最短，那么他们同时获胜）。

    比赛开始之前，我们已经知道有n个人要参加比赛。第i个人游泳的速度是si米每秒，跑步速度是ri米每秒。但是R和S的具体值并不知道，只知道他们是大于0的实数。

    所以我们现在想要知道谁可能获胜。

    Solution

    这是Bouvardia上课时听来的题，思路很巧妙呢。

    确定一项的长度，若总长固定，则另一项可定，接着把选手获胜的不等式写出来，发现可以调整为直线的斜截式。但不需要线性规划或者半平面交，我们求一个凸壳就可以了，构成凸壳的直线就是可能的选手。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    #include <cctype>

    using std::min;
    using std::max;
    using std::sort;
    using std::swap;
    using std::memset;
    using std::isdigit;

    const int maxn = 2e+5 + 5;
    const double eps = 1e-8;

    int n;
    double s[maxn], r[maxn];

    struct Point
    {
    	int x, y;
    	//plus
    	int id;
    	Point(int x_ = 0.0, int y_ = 0.0):x(x_), y(y_){}
    }p[maxn];
    int top, q[maxn], v[maxn];

    bool cmp1(Point p_, Point q_)
    {
    	return p_.x == q_.x ? p_.y > q_.y : p_.x > q_.x;
    }
    bool cmp2(Point p_, Point q_)
    {
    	return p_.x == q_.x ? p_.y > q_.y : p_.x < q_.x;
    }
    inline double k(Point p_, Point q_)
    {
    	return (1.0/q_.y - 1.0/p_.y) / (1.0/p_.x - 1.0/q_.x);
    }
    inline int rd()
    {
    	int x = 0; char c = getchar();
    	while(!isdigit(c)) c = getchar();
    	while(isdigit(c))x = x * 10 + (c ^ 48), c = getchar();
    	return x;
    }
    inline void write(int x)
    {
    	int y = 10, len = 1;
    	while(y <= x) y *= 10, ++len;
    	while(len--) {y /= 10; putchar(x / y + 48); x %= y;}
    }

    int main()
    {
    	n = rd();
    	for(register int i = 1; i <= n; ++i)
    		p[i].x = rd(), p[i].y = rd(), p[i].id = i;
    	sort(p + 1, p + 1 + n, cmp1);
    	int tot = 0, lst = 0;
    	for(register int i = 1; i <= n; ++i)
    	{
    		if(p[i].y > lst || (p[i].y == lst && p[i].x == p[tot].x)) p[++tot] = p[i];
    		lst = max(lst, p[i].y);
    	}
    	n = tot;
    	sort(p + 1, p + 1 + n, cmp2);
    	int top = 1; q[1] = 1;
    	for(register int i = 2; i <= n; ++i)
    	{
    		while(top >= 1 && k(p[i], p[q[top]]) < k(p[q[top]], p[q[top - 1]])) --top;
    		q[++top] = i;
    	}
    	for(register int i = 1; i <= top; ++i) v[i] = p[q[i]].id;
    	sort(v + 1, v + 1 + top);
    	for(register int i = 1; i <= top; ++i) write(v[i]), putchar(' ');
    	return 0;
    }

    Practical Usage

    CodeM 2018 Final F

    Description

    袋鼠先生在玩一个塔防游戏。这个游戏中，一共有n个防御塔，第i个塔位于(xi,yi)的位置，这n个防御塔形成了一个严格的凸多边形。有m道防御网，你可以把第i道防御网看做连接第ui个防御塔和第vi个防御塔的一条线段，穿越它就需要消耗ci的血量。

    袋鼠先生想从(sx, sy)位置走到(tx,ty)位置，他想知道最少要消耗多少血量。

    Solution

    对偶图最短路的点数太多啦.

    观察样例, 发现路径分为两种情况: 走出多边形/在多边形内穿过

    所以我们可以分别来求.

    对于走出多边形, 一定是到达多边形的某条边. 而障碍一定会覆盖一组连续的边. 差分求前缀和就可以得到到达每条边的代价.

    至于内穿, 计算哪些障碍和直线相交, 代价加和就好了.

    判断是否在多边形内部是一个很有用的技能.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    #include <cctype>

    using std::max;
    using std::min;
    using std::swap;
    using std::memset;

    typedef long long ll;

    const int maxn = 1e+5 + 5;
    const double eps = 1e-6;

    int n, m;
    struct point
    {
    	double x, y;
    	point(double x_ = 0, double y_ = 0):x(x_),y(y_){}
    	point operator + (point rhs)
    	{
    		return point(x + rhs.x, y + rhs.y);
    	}
    	point operator - (point rhs)
    	{
    		return point(x - rhs.x, y - rhs.y);
    	}
    	double operator * (point rhs)
    	{
    		return x * rhs.x + y * rhs.y;
    	}
    	double operator ^ (point rhs)
    	{
    		return x * rhs.y - y * rhs.x;
    	}
    }p[maxn], s, t;
    struct line
    {
    	point p, v;
    	line(point p_ = point(), point v_ = point()):
    		p(p_), v(v_) {}
    }l[maxn];
    ll u[maxn], v[maxn], c[maxn];
    ll val[maxn];

    int DCMP(ll x)
    {
    	return x < -eps ? -1 : x > eps;
    }
    inline int rd()
    {
    	int x = 0; bool f = false; char c = getchar();
    	while(!isdigit(c)) { if(c == '-') f = true; c = getchar();}
    	while(isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    	return f ? -x : x;
    }
    inline ll rdll()
    {
    	ll x = 0; bool f = false; char c = getchar();
    	while(!isdigit(c)) { if(c == '-') f = true; c = getchar();}
    	while(isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    	return f ? -x : x;
    }
    inline bool in(point p_)
    {
    	int cnt = 0;
    	for(int i = 1; i <= n; ++i)
    	{
    		int dir = DCMP((p_ - l[i].p)^l[i].v);
    		int dlt1 = DCMP(p[i + 1].y - p_.y);
    		int dlt2 = DCMP(p[i].y - p_.y);
    		if(dir > 0 && dlt1 < 0 && dlt2 >= 0) cnt++;
    		if(dir < 0 && dlt1 >= 0 && dlt2 < 0) cnt--;
    		//printf("%d\n", cnt);
    		//if()
    	}
    	return cnt;
    }
    inline void pre(point p_)
    {
    	//memset(val, 0, sizeof val);
    	for(int i = 1; i <= n; ++i) val[i] = 0;
    	if(!in(p_)) return;
    	for(int i = 1; i <= m; ++i)
    	{
    		line fnc = line(p[u[i]], p[v[i]] - p[u[i]]);
    		int dir = (p_ - fnc.p) ^ fnc.v;
    		if(dir > 0)
    		{
    			val[1] += c[i]; val[u[i]] -= c[i];
    			val[v[i]] += c[i];
    		}
    		else
    		{
    			val[u[i]] += c[i];
    			val[v[i]] -= c[i];
    		}
    	}
    }

    int main()
    {
    	n = rd(); m = rd();
    	for(int i = 1; i <= n; ++i)
    		p[i].x = rdll(), p[i].y = rdll();
    	p[n + 1] = p[1];
    	for(int i = 1; i <= n; ++i)
    	{
    		l[i] = line(p[i], p[i + 1] - p[i]);
    	}
    	for(int i = 1; i <= m; ++i)
    	{
    		u[i] = rdll(), v[i] = rdll();
    		if(u[i] > v[i]) swap(u[i], v[i]);
    		c[i] = rdll();
    	}
    	ll sums = 1e18, sumt = 1e18;
    	s.x = rdll(); s.y = rdll(); pre(s); 
    	for(int i = 1; i <= n; ++i) val[i] += val[i - 1], sums = min(sums, val[i]);
    	t.x = rdll(); t.y = rdll(); pre(t);
    	for(int i = 1; i <= n; ++i) val[i] += val[i - 1], sumt = min(sumt, val[i]);
    	if(!sums)
    	{
    		printf("%lld\n", sumt); return 0;
    	}
    	if(!sumt)
    	{
    		printf("%lld\n", sums); return 0;
    	}
    	ll ans = 0;
    	for(int i = 1; i <= m; ++i)
    	{
    		int dir1 = DCMP((s - p[u[i]]) ^ (p[v[i]] - p[u[i]]));
    		int dir2 = DCMP((t - p[u[i]]) ^ (p[v[i]] - p[u[i]]));
    		if(dir1 * dir2 < 0) ans += c[i];
    	}
    	ans = min(ans, sums + sumt);
    	printf("%lld\n", ans);
    	return 0;
    }