Codeforces Round #358 Div2 E - Alyona and Triangles

問題

Problem - E - Codeforces

平面上に、点がN個あり、どの3点を選んでも三角形を作っても面積がSを超えないように配置されている。このとき、N個の点とは別に3点選び、平面上に配置された全ての点を包含して、かつ、面積が4Sを超えないような三角形を作れ。

解法

uwi さんの解法を参考にした。

結論としては、面積が最大になる三角形を作り、それを4つトライフォースっぽい感じに並べた三角形を返せば良い。下の図で、オレンジの三角形が最大の三角形、赤の三角形が全ての点を内包する三角形である。

もし赤色の三角形の外には点が存在した場合、黄色の三角形よりも大きい三角形が作れてしまうため、黄色の三角形が最大の三角形でなくなってしまう。よって、赤色の三角形の外には点は存在しない。よって、赤色の三角形が条件を満たす三角形である。

最大の三角形は、凸包を作り、二点を全探索して残り一点はしゃくとり法で求めてやれば、で求めることができる。

コード

public class E {
  private static class Task {
    void solve(FastScanner in, PrintWriter out) {
      int N = in.nextInt();
      long S = in.nextLong();
      Long[][] xy = new Long[N][];
      for (int i = 0; i < N; i++) xy[i] = new Long[]{in.nextLong(), in.nextLong()};

      ArrayList<Long[]> convexHull = ConvexHull.run(xy);
      long max = -1L;
      int ti = -1, tj = -1, tk = -1;
      int m = convexHull.size();
      for (int i = 0; i < m; i++) {
        int k = i;
        for (int j = i; j < m; j++) {
          if (k < j) k = j;
          long now = S(convexHull.get(i), convexHull.get(j), convexHull.get(k));
          while (k + 1 < m) {
            long next = S(convexHull.get(i), convexHull.get(j), convexHull.get(k + 1));
            if (next > now) {
              now = next;
              k++;
            } else {
              break;
            }
          }
          if (now > max) {
            max = now;
            ti = i;
            tj = j;
            tk = k;
          }
        }
      }
      Long[] pi = convexHull.get(ti), pj = convexHull.get(tj), pk = convexHull.get(tk);

      long ax = pi[0] + (pj[0] - pi[0]) + (pk[0] - pi[0]);
      long ay = pi[1] + (pj[1] - pi[1]) + (pk[1] - pi[1]);
      long bx = pi[0] + (pj[0] - pi[0]) - (pk[0] - pi[0]);
      long by = pi[1] + (pj[1] - pi[1]) - (pk[1] - pi[1]);
      long cx = pi[0] - (pj[0] - pi[0]) + (pk[0] - pi[0]);
      long cy = pi[1] - (pj[1] - pi[1]) + (pk[1] - pi[1]);
      out.println(ax + " " + ay);
      out.println(bx + " " + by);
      out.println(cx + " " + cy);
    }

    //abcを結んでできる三角形の面積の2倍を返す
    long S(Long[] a, Long[] b, Long[] c) {
      long vx = b[0] - a[0];
      long vy = b[1] - a[1];
      long wx = c[0] - a[0];
      long wy = c[1] - a[1];
      return Math.abs(vx * wy - vy * wx);
    }

  }

  static class ConvexHull {
    public static <T extends Number> ArrayList<T[]> run(T[][] xy) {
      int N = xy.length;
      if (N <= 1) {
        ArrayList<T[]> list = new ArrayList<>();
        Collections.addAll(list, xy);
        return list;
      }
      Arrays.sort(xy, new Comparator<T[]>() {
        @Override
        public int compare(T[] a, T[] b) {
          if (!a[0].equals(b[0])) return Double.compare(a[0].doubleValue(), b[0].doubleValue());
          return Double.compare(a[1].doubleValue(), b[1].doubleValue());
        }
      });

      int[] qs = new int[N * 2];//構築中の凸包
      int k = 0;//凸包の頂点数
      for (int i = 0; i < N; i++) {
        if (k >= 1 && xy[qs[k - 1]][0].equals(xy[i][0]) && xy[qs[k - 1]][1].equals(xy[i][1])) continue;
        while (k > 1 && ccw(xy[qs[k - 2]], xy[qs[k - 1]], xy[i]) > 0) k--;
        qs[k++] = i;
      }

      int inf = k + 1;
      for (int i = N - 2; i >= 0; i--) {
        if (xy[qs[k - 1]][0] == xy[i][0] && xy[qs[k - 1]][1] == xy[i][1]) continue;
        while (k >= inf && ccw(xy[qs[k - 2]], xy[qs[k - 1]], xy[i]) > 0) k--;
        qs[k++] = i;
      }

      ArrayList<T[]> ret = new ArrayList<>(k - 1);
      for (int i = 0; i < k - 1; i++) ret.add(xy[qs[i]]);
      return ret;
    }

    private static <T extends Number> double ccw(T[] a, T[] b, T[] t) {
      return (t[0].doubleValue() - a[0].doubleValue()) * (b[1].doubleValue()
        - a[1].doubleValue()) - (b[0].doubleValue() - a[0].doubleValue()) * (t[1].doubleValue() - a[1].doubleValue());
    }
  }
}