| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 2048 MB | 49 | 4 | 3 | 6.522% |
You are a member of the research team CPCI (Convex Polygon Computational Investigation), tasked with uncovering the properties of an unknown simple polygon $P$ located on a two-dimensional coordinate plane. The exact coordinates of the polygon $P$ are unknown, but you can use a special equipment that allows you to query the number of intersections between a given query line and $P$.
The polygon $P$ is known to be a convex polygon, meaning every line segment between two points inside the polygon is fully contained within its interior. Additionally, $P$ is non-degenerate, ensuring that its area is strictly greater than zero. The polygon also contains the origin $(0, 0)$ strictly within its interior. All vertices of $P$ have integer coordinates, with each coordinate lying within the range $[-1,024,円 1,023円]$ inclusive.
Write a program to compute the area of the polygon $P$ by invoking a series of queries.
You can query with any straight line $l$ on the coordinate plane by selecting two distinct integer points $(x_1, y_1)$ and $(x_2, y_2)$ on the line $l$. For each query, you will receive the number of intersection points between the line $l$ and the boundary of the polygon $P$.
You are allowed to request at most 4ドル,096円$ queries. Using the intersection counts from these queries, you need to determine the exact area of the polygon $P$.
This is an interactive problem. Your submitted program will interact with an interactor inside the grading server, which reads input from and writes output to your program.
The interaction proceeds in rounds. In each round, your program must first write a line containing one of two types of requests as follows:
? $x_1$ $y_1$ $x_2$ $y_2$”
?’, followed by four integers $x_1,ドル $y_1,ドル $x_2,ドル and $y_2$.! $area$”
!’, followed by a real number $area$.After the request is asked, an input line is followed, containing the response of the interactor to your request, and the response is available on standard input. If your request is a query, the response will be an integer representing the number of intersection points. If there are infinitely many intersection points, the response will be “infinity”. If your request is a final output, the response will be “correct” if $area$ is within an absolute error of 10ドル^{-3}$ of the actual area. Otherwise, the response will be “wrong”.
If your program violates the interaction protocol (e.g., issues a malformed request or makes more than 4ドル,096円$ queries), the interactor will immediately terminate the interaction. Also, your program must request exactly one final output, and this must be the last request. After making the output request, your program must terminate gracefully. Do not forget to flush the output after each request.
The polygon $P$ is fixed throughout the interaction; the interactor is not adaptive.
The time and memory used by the interactor is also included in the calculation of your program’s execution time and memory usage. You can assume that the maximum time used by the interactor is 1 second and the maximum amount of memory is 4 MiB.
2 0 1 infinity correct
? 0 0 1 1 ? -3 -1 0 2 ? 0 -4 4 0 ? 4 3 7 5 ! 5.5
In this example, the coordinates of the polygon $P$ were $(1, 1),ドル $(-2, -1),ドル and $(2, -2)$.
To flush, you need to do the following right after writing a request and a line break:
fflush(stdout) in C;std::cout << std::flush in C++;System.out.flush() in Java;sys.stdout.flush() in Python.A testing tool is provided to help you develop your solution, so it is not mandatory to use it. If you want to use it, you can download the attachment testing_tool.py. You can run python3 testing_tool.py -f input.in ./sol to see how your program interacts for a specific polygon $P$. This testing tool can be used regardless of the language of your program as follows: the same explanation is also found in the comments of testing_tool.py.
Usage: python3 testing_tool.py -f inputfile <program>
Use the -f parameter to specify the input file, e.g. input.in.
Format of the input file: The first line contains an integer $n$ ($≥ 3$) that is the number of vertices of the polygon $P$. Each of the next $n$ lines contains two integers $x_i$ and $y_i$ that are $x$- and $y$-coordinates of the $i$-th vertex of $P,ドル respectively. The coordinates of the vertices of $P$ must be given in counterclockwise order.
Example: A triangle ($n = 3$) with vertices $(1, 1),ドル $(-2, -1),ドル $(2, -2)$ given in counterclockwise order.
3 1 1 -2 -1 2 -2
If you have a C++ solution stored in a file called "sol.cpp", you must first compile using "g++ sol.cpp -o sol" and then invoke the testing tool with:
python3 testing_tool.py -f input.in ./sol
If you have a Python solution that you would run using "pypy3 solution.py", you could invoke the testing tool with:
python3 testing_tool.py -f input.in pypy3 solution.py
If you have a Java solution that you would run using "java MyClass", you could invoke the testing tool with:
python3 testing_tool.py -f input.in java MyClass
The tool is provided as-is, and you should feel free to make whatever alterations or augmentations you like to it. Note that it is not guaranteed that a program that passes the testing tool will be accepted.
ICPC > Regionals > Asia Pacific > Korea > Nationwide Internet Competition > Seoul Nationalwide Internet Competition 2024 I번