Tags: ppc

Rating: 0

# Land-1
PPC, 278 Points

Author: lys0829

Writeup By: **mayawan**

## Description
You can ask 128 times. Can you solve this problem?

Remote Server: Ubuntu 18.04

This is a programming contest problem. And the problem type is Special Judge.
The release.zip is some code for you to let you can test on your own computer.
but all the global variable in grader.c is still in the judge server's grader.c.
Your goal is to write a C code and submit it to the system to get Accepted.
If you get Accepted, then you can get the Flag. Please don't attack the Judge System.
But you can attack the problem by your C code.
You must wait for 2 minute between every submission.

## Challenge
There is square Cartesian coordinate plane bound between 0 to 10^9.
Inside of the plane is a rectangle that is bound between x1, x2, y1, y2 ( 0 <= x1 < x2 <= 10^9, 0 <= y1 < y2 <= 10^9).

Using the area(int x1, int y1, int x2, int y2) function, you can find the intersecting area of the rectangle and the rectangle created by the parameters.
You can call this function at most 128 times.

Find the values of x1, x2, y1, y2 of the rectangle
and store them in the rectangle class in a, b, c, d respectively while calling the area function at most 128 times.

## Solution
Begin by finding the total area of the rectangle by calling area(0,0, 1000000000, 1000000000).

If total is 10^18, then the rectangle must be 0, 0, 1000000000, 1000000000

Then do two binary searches to find the lower bounds (x1 and y1) of the rectangle.
***
Initial Condition: lb = 1, rb = 99999999

Termination: lb > rb

Searching left: rb = mid - 1

Searching right: lb = mid + 1
***
With each iteration of the binary searches,
you check area(mid, 0, 1000000000, 1000000000) < total for searching x1
and area(0, mid, 1000000000, 1000000000) < total for searching y1.
If true, search the left half.
If false, search the right half.
x1 and y1 will be the the highest value of mid that results in a false.

The reason why the bounds are 1 and 99999999 is because the judge checks the parameters of the area function.
If x1 >= x2 || y1 >= y2, it is an invalid query and results in a wrong answer.

Once the lower bounds have been found, then find the change of area between total and x1 + 1.
This value (size_y) will be the size of the rectangle in the y direction.
Dividing total by size_y will get you the size of the rectangle in the x direction.
x1 + size_x will result in x2 and y1 + size_y will result in y2.

Now you have all the values and they must be stored into rectangle.

Worst case scenario is 62 calls.

You can find my solution [here](https://github.com/cnbtwriteups/BambooFoxCTF/blob/master/Land.c)