[CQOI2017]小Q的草稿
题号:NC19947
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

小Q是个程序员。众所周知,程序员在写程序的时候经常需要草稿纸。小Q现在需要一张草稿纸用来画图,但是桌上 只有一张草稿纸,而且是一张被用过很多次的草稿纸。草稿纸可以看作一个二维平面,小Q甚至已经给它建立了直角坐标系。以前每一次草稿使用过的区域,都可以近似的看作一个平面上的一个三角形,这个三角形区域的内部和 边界都不能再使用。当然了,以前的草稿也没有出现区域重叠的情况。
小Q已经在草稿纸上画上了一些关键点,这 些关键点都在没使用过的区域。小Q想把这些关键点两两之间尽可能的用线段连接起来。连接两个关键点的线段有 可能会穿过已经用过的草稿区域,这样显然不允许。于是小Q就想知道,有多少对关键点可以被线段连接起来,而 且还不会穿过已经用过的区域。为了方便,小Q保证任意三个关键点不会共线。

输入描述:

第一行包含两个整数V,T,表示草稿纸上的关键点数量和三角形区域数量。
接下来V行,每行两个整数x,y,表示一个关键点的坐标(x,y)。
接下来T行,每行六个整数x1,y1,x2,y2,x3,y3,表示一个三角形区域的三个顶点坐标分别是(x1,y1),(x2,y2),(x3,y3)保证三角形的面积大于0。
V ≤ 1000,T ≤ 1000,0 ≤ 所有坐标 ≤ 10^8且为整数

输出描述:

输出一行,一个整数,表示能够被线段连接起来的关键点有多少对。
示例1

输入

复制
3 0
0 0
2 0
2 2

输出

复制
3

说明

整个草稿纸是全新的,任意两个关键点都可以连线。