#include #include #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; pairP[200002]; for (int i = 0;i < N;i++) { cin >> P[i].first >> P[i].second; } sort(P, P + N);//座標を辞書順ソート stack>top, bot; top.push(P[0]);//上回りで凸包をつくる。 top.push(P[1]); for (int i = 2;i < N;i++) { while (1) { pair top0 = top.top(); top.pop(); if ((top0.first - top.top().first) * (P[i].second - top0.second) - (top0.second - top.top().second) * (P[i].first - top0.first) < 0) {//ベクトルの外積で内角が180度以上になるか判定 top.push(top0);//内角が180度未満の場合、採用。 top.push(P[i]); break; } else if (top.size() == 1) { top.push(P[i]); break; } } } bot.push(P[0]);//下回りで凸包をつくる。 bot.push(P[1]); for (int i = 2;i < N;i++) { while (1) { pair top0 = bot.top(); bot.pop(); if ((top0.first - bot.top().first) * (P[i].second - top0.second) - (top0.second - bot.top().second) * (P[i].first - top0.first) > 0) {//ベクトルの外積で内角が180度以上になるか判定 bot.push(top0);//内角が180度未満の場合、採用。 bot.push(P[i]); break; } else if (bot.size() == 1) { bot.push(P[i]); break; } } } while (bot.top() == top.top()) { bot.pop(); } vector>R; while (!top.empty()) { R.push_back(top.top()); top.pop(); } reverse(R.begin(), R.end()); while (!bot.empty()) { R.push_back(bot.top()); bot.pop(); } //Rには時計回り順に各頂点を訪問するときの経路(P[0]は始点及び終点とする)が入っている。 //もし気になるなら全部チェックして内角を測り180度未満なことを確認してもよい。 if (R.size() == N + 1) {//外周を凸包で囲んだときに点が足りているか cout << "Yes\n"; } else { cout << "No\n"; } return 0; }