CF46G Emperor's Problem

这发生在伟大的 Berland 帝国时期。一次，皇帝梦见神使传来神谕，命令建造一座基座为有 $n$ 个角的凸多边形的神庙。第二天早晨，皇帝便下令修建一座正 $n$ 边形基座的神庙。神庙建成后不久，帝国便遭受了灾难和歉收。在一次地震摧毁了神庙后，皇帝明白自己或许惹怒了众神，导致灾祸降临。于是他下令召见智者。当智者到来时，皇帝将梦境讲给他听，并问道：“至智者啊，告诉我，我何以惹怒众神？”智者答道：“陛下，依我之见，神灵盛怒，是因陛下过于草率，未听完神谕便仓促行事。” 果然，在接下来的夜晚，神使再次出现，责备皇帝选择了一个不完美的形状建造神庙。“但还有比正多边形更完美的形状吗？”皇帝在梦中呼喊。神使这才把神谕讲完： - 多边形的所有顶点都应位于格点上。 - 所有边的长度都要互不相同。 - 在满足这些条件的多边形中，应选择最大边最小的那个。 你是一名忠诚的建筑师，需要绘制神庙的设计图。请注意，多边形应为简单多边形（边界不自交或重合）、凸多边形，允许有三点共线。

第一行为一个整数 $n$，表示多边形的边数（$3 \leq n \leq 10000$）。

如果可以构造满足条件的多边形，第一行输出"YES"（不带引号）。接下来 $n$ 行，每行输出两个整数，依逆时针顺序给出多边形各个顶点的坐标。坐标的绝对值不得超过 $10^9$，任意两个顶点不能重合。你可以输出任意一个可行解。 如果无法构造，输出"NO"（不带引号）。

由 ChatGPT 5 翻译