I_love_a0666's blog

Triangles — Kattis Problem
By I_love_a0666, history, 8 years ago, In English

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.

  • Vote: I like it
  • +45
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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).

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you elaborate some more on your approach?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 5   Vote: I like it +8 Vote: I do not like it

      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]

      → Reply
»
8 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Nice username.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your response!

    It seems that there is no nice and clean way to solve this problem.

    → Reply