A85858.「CQOI2017」小 Q 的草稿
NOI/NOI+/CTSC
通过率:0%
时间限制:3.00s
内存限制:128MB
题目描述
小 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。
输出格式
输出一行,一个整数,表示能够被线段连接起来的关键点有多少对。
输入输出样例
输入#1
3 0 0 0 2 0 2 2
输出#1
3
输入#2
3 1 0 0 2 0 2 2 1 0 1 1 2 1
输出#2
0
说明/提示
对于 100% 的测试点,1≤V,T≤1000,0≤xi,yi≤108,且都是整数。