1963 . 千湖之路2
TopCoder
Description
建康中學（簡稱建中）是傳說中的「千湖中學」。既然處處都是湖，自然就會有青蛙囉！
在建中裡，有$n$隻青蛙，每隻青蛙都想要在一條直線上跳躍，從直線的一端跳到另一端。除此之外，這$n$條直線中沒有平行的線，也沒有共點的三條線。然而中間是個汪洋大湖，所以他們在湖中只能停在石頭上（在任兩條直線的交點處都會有一顆石頭）。
有一天，這$n$隻青蛙突發奇想，想來跳一支舞。為了完成這支舞，這$n$隻青蛙必須從他們所在的直線的某一端，整齊劃一地跳到另一端。具體地說，每過一拍，每隻青蛙都要跳到下一顆石頭，直到跳到另一端為止。
當然，如果有兩隻青蛙同時停在同一個石頭上，其中一隻青蛙就會被擠到水裡，舞就跳不成了。因此這$n$隻青蛙想找出所有的跳法，使得任兩隻青蛙都不會同時停在同一個石頭上。
Input Format
第一行有一個正整數$2\leq n\leq 10^ 4$，代表青蛙的個數。
接下來的$n$行中每行都有兩個絕對值不超過$10^ 4$的整數$a,b$以及一個絕對值不超過$10^ 8$的整數$c$， 其中$b\neq 0$，代表有一隻青蛙要在直線$ax+by=c$上跳躍。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~4) | $n\leq 15$ | 15 |
| 2 (5~9) | $n$是偶數 | 25 |
| 3 (0~14) | 無 | 30 |
| 4 (0~19) | 時限縮短 | 30 |
Output Format
第一行請輸出一個非負整數，代表所有滿足題目條件的跳法有幾種。
若第一行的數字非零，請在第二行輸出長度為$n$的01字串，代表其中一種可行的方法。其中第$i$個位置是0代表第$i$隻青蛙要從直線的左端開始往右跳，是1代表要從右端開始往左跳。
Sample Input 1
2
1 1 1
1 2 3
1 1 1
1 2 3
Sample Output 1
0
Sample Input 2
5
1 1 1
2 -1 5
1 2 7
2 -5 6
29 -1 87
1 1 1
2 -1 5
1 2 7
2 -5 6
29 -1 87
Sample Output 2
2
01100
01100
Hints
範例測資2的一個可行方案如下：
Problem Source
Problem/Description by Paupière
改編自2016 IMO P6
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 15 |
| 2 | 5~9 | 25 |
| 3 | 0~14 | 30 |
| 4 | 0~19 | 30 |