Preparing NOJ

Sdl and Interview Questions

1000ms 262144K

Description:

There are new players entering the pit! SDL is responsible for interviewing new players this time. I remember that the last time SDL made a cute sister give up because of the problem of network flow directly during the interview. So this time, SDL only asked a simple question:

There are n points in the coordinate system, you need to divide these points into several groups (each group is independent), do the following operations for each group:

  1. For each point $$$(x_i, y_i)$$$ in the group, draw two lines $$$x=x_i$$$ and $$$y=y_i$$$.
  2. When all the points have completed this operation, extract the intersection of all the lines(If there are multiple lines that coincide, then only one is processed).
  3. The core point we define for this group is the one of the intersections that is furthest from the origin $$$(0,0)$$$ of the coordinate axis.
  4. Put the core points of this group after you have been grouped into a collection called "SdlSet".
  5. Remove all lines.

After all the groups have completed the above operations, we have several core points in the SdlSet (the number of core points is derived from the number of groups you have divided).

Rest assured, SDL does not let you find the core points of each group. He asked you to make a reasonable division plan to minimize $$\displaystyle \sum_{(x,y)\in SdlSet}xy$$

Your task is to give this minimum so you can pass the Sdl interview.

Input:

The first line of the input contains an integer$$$n(1\leq n \leq 2\cdot 10^5)$$$, denoting the number of points.

In the second line, there are $$$n$$$ pairs $$$(x_1,y_1)$$$,$$$(x_2,y_2)\cdots$$$,$$$(x_n,y_n)$$$ $$$(1\leq x_i,y_i \leq 10^9)$$$,denoting coordinates of each point.

Output:

Print a single line containing an integer, denoting the minimum value that sdl want.

Sample Input:

4
1 10
3 3
4 2
10 1

Sample Output:

32

Note:

If the group is assigned as follows: Group 1: (1,10) Group 2: (10,1) Group 3: (3,3), (4,2) SdlSet: (1,10), (10,1), (4,3) So the answer is $$$1\times 10+10\times1+4\times3=32 $$$

Info

NOJ

Provider NOJ

Code NOJ2391

Tags

Submitted 7

Passed 5

AC Rate 71.43%

Date 08/16/2019 01:50:45

Related

Nothing Yet