Codeforces Educational 1F - Cut Length

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 0.5s
Memory limit: 256M

Suggester:
Problem source:
Codeforces Educational 1
Problem type
Allowed languages
C, C++, Java, Pascal, Python

Cho một đa giác ~n~ điểm và không tự cắt chính nó. Đa giác có thể không lồi và có thể chứa góc ~180~ độ.

Cho ~m~ đường thẳng. Với mỗi đường thẳng, hãy tìm độ dài của phần chung giữa đường thẳng đó và đa giác đã cho.

Input

Dòng đầu tiên chứa các số nguyên ~n~ và ~m~ ~(3 \le n \le 1000; 1 \le m \le 100)~.

~n~ dòng tiếp theo, mỗi dòng ghi toạ độ các điểm của đa giác (theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ). Các điểm phân biệt với nhau.

~m~ dòng tiếp theo, mỗi dòng gồm toạ độ hai điểm phân biệt trên đường thẳng, mô tả đường thẳng đó.

Mọi toạ độ trong input đều là số thực với tối đa ~2~ chữ số ở phần thập phân. Ngoài ra, các toạ độ này có giá trị tuyệt đối không quá ~10^5~.

Output

In ra ~m~ dòng, dòng thứ ~i~ chứa độ dài của phần chung giữa đường thẳng thứ ~i~ và đa giác. Đáp án sẽ được tính là đúng nếu sai số không vượt quá ~10^{-6}~.

Sample Input

4 3
0 0
1 0
1 1
0 1
0 0 1 1
0 0 0 1
0 0 1 -1

Sample Output

1.41421356237309514547
1.00000000000000000000
0.00000000000000000000

Comments

Please read the guidelines before commenting.


There are no comments at the moment.