結果

問題 No.3154 convex polygon judge
ユーザー tnakao0123
提出日時 2025-05-21 15:26:14
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 72 ms / 2,000 ms
コード長 2,475 bytes
コンパイル時間 1,027 ms
コンパイル使用メモリ 64,788 KB
実行使用メモリ 12,840 KB
最終ジャッジ日時 2025-05-21 15:26:18
合計ジャッジ時間 3,281 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 44
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:98:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   98 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
main.cpp:102:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  102 |     scanf("%lld%lld", &ps[i].x, &ps[i].y);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 3154.cc:  No.3154 convex polygon judge - yukicoder
 */

#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

/* constant */

const int MAX_N = 200000;

/* typedef */

using ll = long long;

template <typename T>
struct Pt {
  T x, y;
  Pt() {}
  Pt(T _x, T _y) : x(_x), y(_y) {}
  Pt(const Pt<T> &p) : x(p.x), y(p.y) {}

  Pt<T> operator+(const Pt<T> p) const { return Pt<T>(x + p.x, y + p.y); }
  Pt<T> operator-() const { return Pt<T>(-x, -y); }
  Pt<T> operator-(const Pt<T> p) const { return Pt<T>(x - p.x, y - p.y); }
  Pt<T> operator*(T t) const { return Pt<T>(x * t, y * t); }
  Pt<T> operator/(T t) const { return Pt<T>(x / t, y / t); }
  T dot(Pt<T> v) const { return x * v.x + y * v.y; }
  T cross(Pt<T> v) const { return x * v.y - y * v.x; }
  T d2() { return x * x + y * y; }

  Pt<T> rot90() { return Pt<T>(-y, x); }

  bool operator==(const Pt<T> pt) const { return x == pt.x && y == pt.y; }
  bool operator<(const Pt<T> &pt) const {
    return x < pt.x || (x == pt.x && y < pt.y);
  }

  void print() { printf("(%d,%d)", x, y); }
};

using pt = Pt<ll>;
using vpt = vector<pt>;

/* global variables */

/* subroutines */

// convex_hull()
//   make a convex_hull 'chs' from a set of points 'ps'
//   Note: ps must be sorted, and must contain at least 2 points
vpt convex_hull(const vpt& ps) {
  int n = ps.size();
  vpt lhs, uhs;

  lhs.push_back(ps[0]);
  lhs.push_back(ps[1]);
  for (int i = 2; i < n; i++) {
    while (lhs.size() >= 2) {
      int ln = lhs.size();
      pt &lh0 = lhs[ln - 2], &lh1 = lhs[ln - 1];
      if ((lh1 - lh0).cross(ps[i] - lh1) > 0) break;
      lhs.pop_back();
    }
    lhs.push_back(ps[i]);
  }

  uhs.push_back(ps[n - 1]);
  uhs.push_back(ps[n - 2]);
  for (int i = n - 3; i >= 0; i--) {
    while (uhs.size() >= 2) {
      int un = uhs.size();
      pt &uh0 = uhs[un - 2], &uh1 = uhs[un - 1];
      if ((uh1 - uh0).cross(ps[i] - uh1) > 0) break;
      uhs.pop_back();
    }
    uhs.push_back(ps[i]);
  }

  lhs.pop_back();
  uhs.pop_back();

  vpt chs;
  chs.reserve(lhs.size() + uhs.size());
  chs.assign(lhs.begin(), lhs.end());
  chs.insert(chs.end(), uhs.begin(), uhs.end());
  return chs;
}

/* main */

int main() {
  int n;
  scanf("%d", &n);

  vpt ps(n);
  for (int i = 0; i < n; i++)
    scanf("%lld%lld", &ps[i].x, &ps[i].y);
  sort(ps.begin(), ps.end());

  auto chs = convex_hull(ps);

  if (chs.size() == n) puts("Yes");
  else puts("No");
  
  return 0;
}
0