首页 > ACM题库 > HDU-杭电 > hdu 4761 Sky待解决[解题报告]C++
2015
09-17

hdu 4761 Sky待解决[解题报告]C++

Sky

问题描述 :

Little Qiang is watching the night sky after completing his math homework. After staring boringly at the sky for a while, he observes that actually many stars are lying on identical lines, so that a few number of parallel lines are suffice to cover all the stars in the sky. Being passionate about both astronomy and math, he decides to find out the minimum number of parallel lines to achieve the full coverage of stars. Moreover, the stars appear and disappear from time to time, making the problem more interesting.

Specifically, we assume that the stars are numbered from 1 to N. Initially, there are no stars in the sky. Then the sky will be refreshed for M rounds. For each round, one star will appear/disappear, and Little Qiang will compute again the result. Note that the same star could appear/disappear for more than once.

Unfortunately, Little Qiang has Trypophobia such that he cannot insist looking at the sky for a long period to finish the entire task. What a pity! Can you help him?

Good Firewall

(The figure shows a concrete snapshot of the sky, where 3 parallel lines (the blue lines) are sufficed to cover all the 6 stars.)

输入:

There are multiple test cases. For each test case, there will be two integers N (1<=N<=500) and M (1<=M<=1000) in the first line as stated above. Each of the following N lines has two integers x and y (-1000000 < x, y < 1000000), indicating the coordinates of each star (from 1 to N). Then M lines follows, representing M rounds of refreshes of the sky. Each of the M lines has two integers a and b, where a = 0/1 means that b-th (1<=b<=N) star appears/disappears in the sky. Your program should proceed to the end of file.

You can assume that an appeared star would not appear again before its next disappearance, and a disappeared star would not disappear again before its next appearance.

输出:

There are multiple test cases. For each test case, there will be two integers N (1<=N<=500) and M (1<=M<=1000) in the first line as stated above. Each of the following N lines has two integers x and y (-1000000 < x, y < 1000000), indicating the coordinates of each star (from 1 to N). Then M lines follows, representing M rounds of refreshes of the sky. Each of the M lines has two integers a and b, where a = 0/1 means that b-th (1<=b<=N) star appears/disappears in the sky. Your program should proceed to the end of file.

You can assume that an appeared star would not appear again before its next disappearance, and a disappeared star would not disappear again before its next appearance.

样例输入:

4 6
0 0
0 1
0 2
1 1
0 1
0 3
0 2
0 4
1 2
1 1

样例输出:

1
1
1
2
2
1