Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Split convex polygon
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 630Accepted: 187

Description

Two polygons on a plane are described by the coordinates of their vertices in anticlockwise order. The polygons are otherwise arbitrary but it is known that no three sequential vertices lie on the same line. It is suspected that the two polygons are parts of one bigger convex polygon that was split in two.

Write a program to check the guess on the condition that it is allowed to move and rotate, but not to invert the parts to match them together. All computations should be made with the precision of 0.001.

Input

The first line contains an integer N1 (3≤N1≤100) – the number of vertices of the first polygon. Each of the following N1 lines contains two real numbers X, Y separated by one space – the coordinates of one vertex. The rest of the file describes the second polygon in similar manner.

Output

The first and only line of the output must contain the number 1 if the guess is correct, and 0 otherwise.

Sample Input

7
0 0
4 0
4 1
3 3.5
4 4
4 5
0 5
7
6 0
11 0
11 4
10 4
9.5 5
7 4
6 4

Sample Output

1

Source

Northeastern Europe 2002, Western Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator