SIR, 100 points
레이팅 미적용의견: 0
CROATIAN OLYMPIAD IN INFORMATICS 2015
Time limit: 1 second
Memory limit: 512 MB
Page \(1/2\)
Krešo has bought some delicious cheese with peppers, but Stjepan doesn’t really like peppers so he’s trying
to cut a piece that doesn’t contain any peppers.
Krešo’s cheese has the shape of a convex polygon, and each pepper is one point on the inside of the polygon.
Stjepan cuts the cheese exactly once in such a way that he chooses two vertices of the polygon that are
not adjacent and cuts along the line segment connecting them. Stjepan then takes the freshly cut part
without any peppers (on the inside nor on the edges).
The image corresponds \(to\) the first sample test. The dotted line marks Stjepan’s cut.
Write a programme that will determine whether Stjepan can cut a piece of cheese without any peppers. If
he can, determine the maximum possible area of the piece of cheese without peppers that Stjepan can
cut.
subtask
subscore
constraints
1
12
4 ⩽\(N\) ⩽300, 1 ⩽\(M\) ⩽300
2
39
4 ⩽\(N\) ⩽3 000, 1 ⩽\(M\) ⩽3 000
3
49
4 ⩽\(N\) ⩽300 000, 1 ⩽\(M\) ⩽300 000
In all subtasks, the coordinates will be from the interval [−\(10^{9}\), \(10^{9}\)].
The first line of input contains the integer \(N\) – the number of vertices of the convex polygon representing
the cheese.
Each of the following \(N\) lines contains two integers \(X@@RISE_MATH_BLOCK_0@@i\) – coordinates of the \(i\)^{th} polygon vertex.
The following line contains the integer \(M\) – the number of peppers.
Each of the following \(M\) lines contains two integers \(X@@RISE_MATH_BLOCK_1@@i\) – coordinates of the \(i\)^{th} peppers.
The polygon vertices are given in count\(er-cl\)ockwise order and form a convex polygon. None two adjacent
edges are parallel.
All peppers are located in different coordinates in the inside of the polygon (they will not be located on the
edge or outside of the polygon).
The first and only line of output must contain an integer – twice the maximum possible area (the double
area is always going to be an integer).
If it isn’t possible to cut a piece of cheese without peppers in one move, output 0.
CROATIAN OLYMPIAD IN INFORMATICS 2015
Time limit: 1 second
Memory limit: 512 MB
Page \(2/2\)
5
0 1
3 0
4 2
2 3
0 3
3
2 1
3 1
3 2
6
-3 3
-3 -4
-2 -5
2 -5
3 -4
3 3
7
1 0
0 -1
0 -3
2 0
0 0
0 2
-1 0
6
0 3
-1 2
-1 -2
0 -3
1 -2
1 2
1
0 0output
output
4
10
4Clarification of the second example: Stjepan cuts from vertex 2 to vertex 5.
Clarification of the third example: Stjepan cuts from vertex 1 to vertex 3.
평가 및 의견
SIR, 100 points
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
SIR, 100 points