| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 11 | 8 | 8 | 100.000% |
You are given a particle collision energy generator. The generator is a two-dimensional field with N towers. The ith tower is located at position (Xi, Yi), and all towers have the same field of effect with a radius of R.
Each tower radiates 4 types of particles at a fixed configuration. Specifically, each tower radiates each particle A, B, C, and D on its own quadrant (area separated by both its x-axis and y-axis) in a clockwise order, respectively. The tower does not radiate any particle at its x-axis or y-axis.
Initially, each tower is oriented at a multiple of 90◦ angle. Let ( · , · , · , · ) represents the particles radiated by a tower on its upper right, lower right, lower left, and upper left quadrant, respectively.
An interesting phenomenon might occur on the ith tower when there is a jth tower such that the following conditions are satisfied.
The interesting phenomenon is as follow. Let p be the particle that is radiated by the ith tower on the quadrant where the jth tower is located, and q be the particle that is radiated by the jth tower on the quadrant where the ith tower is located. For simplicity, let’s say <p, q> are the particles radiated by their facing sides.
This phenomenon applies both ways (from each tower’s perspective) and stacks indefinitely if there are multiple towers satisfying the conditions.
Here are some examples of the energy generated from a pair of towers.
Each tower also passively generates its own energy. Initially, each tower generates P energy by itself.
You have the option to change the orientation of each tower by rotating it, possibly taking advantage of the interesting phenomenon and increasing the total amount of energy generated. Each 90◦ rotation in any direction (either CW/clockwise or CCW/counterclockwise) causes the tower to produce P less energy passively. A tower that is rotated 90◦ in any direction will produce 0 energy passively and a tower that is rotated 180◦ (rotated 90◦ twice in the same direction) will produce −P energy (or in other words, consume P energy). Note that you can only rotate any tower by a multiple of 90◦.
Your task in this problem is to find the maximum amount of total energy that can be generated by changing the orientation of zero or more towers in any way. The total energy generated in a configuration is the sum of energy generated by each tower either passively or due to interaction with another tower in the configuration.
Input begins with a line containing 4 integers N R G P (1 ≤ N ≤ 50; 1 ≤ R, G, P ≤ 1000) representing the number of towers, the radius of effect of all towers, the tower interaction energy constant, and the initial energy passively generated by each tower, respectively. The following N lines contain 3 integers Xi Yi Oi (−1000 ≤ Xi, Yi ≤ 1000; Oi ∈ {0, 90, 180, 270}) representing the position and the initial orientation of the ith tower. It is guaranteed that no two towers have the same position.
Output contains an integer in a line representing the maximum amount of total energy that can be generated out of all possible configurations of the towers.
3 10 10 15 0 0 0 2 2 180 100 100 180
35
The maximum amount of total generated energy can be obtained by rotating the 2nd tower for 180◦. No interesting phenomenon can happen on the 3th tower as its Euclidean distance to any other towers is larger than R. By not rotating the 3th tower, it generates 15 passive energy. Rotating the 2nd tower for 180◦ will cause it to be oriented at 0◦. An interesting phenomenon occurs on the 1st tower and the 2nd tower as they satisfy all the conditions and their facing side radiates <A, C> (or <C, A> from the 2nd tower’s perspective). The 1st tower will produce 15 + 10 = 25 from its passive energy generation and interaction with the 2nd tower, while the 2nd tower will produce −15 + 10 = −5 energy. These 3 towers generate a total energy of 25 − 5 + 15 = 35 in this configuration.
3 10 1 1000 0 0 0 2 2 0 -4 4 180
2998
The maximum amount of total generated energy can be obtained by not doing any rotation. These 3 towers are interacting with each other at their current orientation. The 1st and 2nd towers each generates 1+(−1) = 0 interaction energy while the 3rd tower generates −1 + (−1) = −2 interaction energy. Each tower also passively generates 1000 energy. The total energy generated in this configuration is 2998.
4 10 1000 1 0 0 0 0 2 90 2 0 180 2 2 270
4002
The maximum amount of total generated energy can be obtained by rotating the 1st tower for 90◦ CCW and the 2nd tower for 90◦ CW. With these rotations, there are only interactions between the 1st and 4th towers, and the 2nd and 3rd towers due to the interesting phenomenon. The 1st tower generates 0 + 1000 = 1000 energy, the 2nd tower generates 0 + 1000 = 1000 energy, the 3rd tower generates 1 + 1000 = 1001 energy, and the 4th tower generates 1 + 1000 = 1001 energy. The total energy generated in this configuration is 4002.