QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 4096 MB Total points: 100
[0]

# 4345. hpmo / 赫露艾斯塔

Statistics

给定 n 个互不相同的点 (xi,yi)m 个集合 Sj={(xi,yi)Ajxi+Bjyi+Cj>0},你需要找出一个 1,2,,m 的排列 p1,p2,,pm,使得 |Sp1|+mi=2|SpiSpi1|MM 是给定的常数,AB 表示 (AB)(AB)

输入格式

第一行两个整数 n,m

接下来 n 行每行两个整数表示 xi,yi

接下来 m 行每行三个整数表示 Aj,Bj,Cj

输出格式

输出 m 行,依次表示 p1,p2,,pm

样例数据

样例 1 输入

5 5
1 1
4 5
1 4
1 9
1 9
1 2 3
4 5 6
7 8 9
1 1 4
5 1 4

样例 1 输出

1
2
3
4
5

样例 2~3

见下发文件。

子任务

注意,使用捆绑测试。

对于 20% 的数据,满足 1n1041m104

对于另外 30% 的数据,满足 xi=yixi=yi

对于 100% 的数据,满足 1n1051m2×105109A,B,C,xi,yi109M=1.8×108,所有输入均为整数。