AtCoder Beginner Contest 178 Tutorial

[utterances-bot]

AtCoder Beginner Contest 178 Tutorial | CP Wiki

lucifer1004's CP notes

https://cp-wiki.vercel.app/en/tutorial/atcoder/ABC178/

[Genius3435]

I did E a bit differently. I don't know how to prove it's optimal, but it intuitively makes sense to me.

We don't need to check most of the points, specifically all of the ones that are "on the inside" of the other points. So we can keep track of the points which are furthest out, and if that ends up only being a small subset of the points, we can easily check those.

So how do we get those points? Well, we want the one that is furthest "up and to the right", "up and to the left", "down and to the right", and "down and to the left". Specifically, we want the points that maximize f(x, y) = x + y, f(x) = -x + y, f(x) = x - y, f(x) = -x - y, respectively. So we can simply find those points in O(N), and check all pairs in O(1).

PS: How do you get LaTeX in Markdown? I've tried $ -- $, \[ -- \], \( -- \), but none of them seem to work.

[lucifer1004]

@Genius3435

I think your method is just the same because you need to check all points to find the 4 maximums.

By the way, the comment system does not support LaTeX AFAIK.