Блог пользователя I_love_a0666

Triangles — Kattis Problem
Автор I_love_a0666, история, 8 лет назад, По-английски

Hello,

I was trying out this problem on Kattis, but I couldn't come up with an efficient solution. It seems like an interesting problem. Here is what the problem basically amounts to:-

Given N (N ≤ 1000000) points on a 2D Plane (0 ≤ xi, yi ≤ 1000000), compute . Here, area(i, j, k) denotes the area of the triangle formed by points i, j, k.

Can someone provide hints?

Thanks in advance.

  • Проголосовать: нравится
  • +45
  • Проголосовать: не нравится

»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Sorry this was for when the sum was over area(i,j,k). I didn't see that it was squared. I'm sorry.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thank you for your response.

    Yes, I figured out how to solve it for that as well. I couldn't quite extend it to sums of squares though and was wondering if there's a nicer solution altogether.

    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

There is very messy way to do it. You can take each term and express it terms of coordinates of i, j, k. Then group up terms so that computation would be O(N).

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Could you elaborate some more on your approach?

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
      ← Rev. 5   Проголосовать: нравится +8 Проголосовать: не нравится

      Sorry for the late post, but this method is perfectly feasible and gets AC. THe steps are extremely messy, but the result is beautiful.

      First, express the answer like so:

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N\frac{(y_i(x_j-x_k)+y_j(x_k-x_i)+y_k(x_i-x_j))^2}{24}$$$

      [Extremely long expansion redacted]

      Then, sum by parts, and reduce the nested sum into products of one-layer sums for each of the 21 summands:

      $$$A=\sum_{i=1}^Nx_i$$$
      $$$B=\sum_{i=1}^Nx_iy_i$$$
      $$$C=\sum_{i=1}^Ny_i$$$
      $$$D=\sum_{i=1}^Nx_i^2$$$
      $$$E=\sum_{i=1}^Ny_i^2$$$

      1

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^Nx_i^2y_j^2$$$
      $$$NDE$$$

      2

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N-2x_i^2y_jy_k$$$
      $$$-2DC^2$$$

      3

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^Nx_i^2y_k^2$$$
      $$$NDE$$$

      4

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N-2x_ix_jy_iy_j$$$
      $$$-2NB^2$$$

      5

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N2x_ix_jy_iy_k$$$
      $$$2ABC$$$

      6

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N2x_ix_jy_jy_k$$$
      $$$2ABC$$$

      7

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N-2x_ix_jy_k^2$$$
      $$$-2EA^2$$$

      8

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N2x_ix_ky_iy_j$$$
      $$$2ABC$$$

      9

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N-2x_ix_ky_iy_k$$$
      $$$-2NB^2$$$

      10

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N-2x_ix_ky_j^2$$$
      $$$-2EA^2$$$

      11

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N2x_ix_ky_jy_k$$$
      $$$2ABC$$$

      12

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^Nx_j^2y_i^2$$$
      $$$NED$$$

      13

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N-2x_j^2y_iy_k$$$
      $$$-2DC^2$$$

      14

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^Nx_j^2y_k^2$$$
      $$$NDE$$$

      15

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N-2x_jx_ky_i^2$$$
      $$$-2EA^2$$$

      16

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N2x_jx_ky_iy_j$$$
      $$$2ABC$$$

      17

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N2x_jx_ky_iy_k$$$
      $$$2ABC$$$

      18

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N-2x_jx_ky_jy_k$$$
      $$$-2NB^2$$$

      19

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^Nx_k^2y_i^2$$$
      $$$NED$$$

      20

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^N-2x_k^2y_iy_j$$$
      $$$-2DC^2$$$

      21

      $$$\sum_{i=1}^N\sum_{j=1}^N\sum_{k=1}^Nx_k^2y_j^2$$$
      $$$NED$$$

      The result is

      $$$6(2ABC+NDE-DC^2-NB^2-EA^2)$$$

      , and dividing by 24 gives

      $$$\frac{2ABC+NDE-DC^2-NB^2-EA^2}{4}$$$

      .

      You need to use Python, though (intermediate steps go past the range of a 128-bit integer)

      [Edit because math equation broke the page] [Edit 2: Latex Gods are not happy]

      → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

Nice username.

→ Ответить
»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

We can express the area of a triangle, given that its vertices are points (x1, y1), (x2, y2), (x3, y3) using the cross product. The formula we get is:

1/2 [(x2-x1)(y3-y1)-(x3-x1)(y2-y1)]

Let us solve the problem for a fixed (x1, y1) and (x2, y2), finding the sum of areas (not of squares of areas) of triangles formed by (x1, y1),(x2, y2), (x_i, y_i) for all i.

Rearranging the terms of the above area equation in order to have the variables x_i and y_i (note that I will be omitting the 1/2 in front, but don't forget to add it back in at the end).

x1y2-x2y1 + y_i(x2-x1) + x_i(y1-y2)

To get sum of all these areas, we can compute sum of all y values, let it be sum_y as well as sum of all x values. Let it be sum_x. The answer is now x1y2 — x2y1 + sum_y * (x2-x1) + sum_x * (y1-y2)

There is a problem with this approach however since the individual result we get from computing the area by cross product is that we can also get negative values. Adding up these values as we do here, withough taking the absolute value, will not produce the correct answer.

The question asks for sum of squares of areas, so the negatives we get will go away and we won't have to worry about this. To deal with squares we compute the square of the equation, getting

sq(x1) * sq(y2) + sq(x2) * sq(y1) + sq(y3) * sq(x2 — x1) + sq(x3) * sq(y1 — y2) — 2*x1*x2*y1*y2 + 2*y3*x1*y2*(x2-x1) + 2*x3*x1*y2*(y1-y2) — 2*y3*x2*y1*(x2-x1) — 2*x3*x2*y1*(y1-y2) + 2*y3*x3*(x2-x1)*(y1-y2)

Where sq(z) is z^2 (I just copied this from some code I wrote to test this, so I didn't change all of the symbols).

We proceed as last time, summing over all possible third point, having a fixed first two points. We will need to pre-compute the

  1. sum of all squares of y coordinates
  2. the sum of all squares of x coordinates
  3. the sum of all values of y coordinates
  4. the sum of all values of x coordinates
  5. the sum of all values of x_i * y_i

These can all be computer in O(N).

Now, let us fix only the first point (x1, y1) and finding the sum of square of areas for all triangles (x1, y1), (x_i, y_i), (x_k, y_k). This is done using the result we have found above, and then performing another summation over k.

Something similar can be done to find sum of all triangles, summing over all possible first points as well.

→ Ответить