计算几何的第一道坎不是算法，而是把图形翻译成代数。这件事只需要两个式子：点积管角度，叉积管方向。把这两个写好，「有没有拐弯」「在左边还是右边」「这块面积是多少」全都变成几次乘法和减法。
出发点是：把点当成向量。点 A、B 的差 A − B 是一条有向线段；两点的「位置」本身没有意义，只有「差」才有。于是整节代码里点与向量共用一个类型，减法得到向量，向量加减还得到向量。
| 运算 | 定义 | 几何意义 | 典型用途 |
|---|---|---|---|
| 加法 / 减法 | (ax±bx, ay±by) | 平移、两点连线 | 把点搬到原点看问题 |
| 点积 dot | ax·bx + ay·by | |a||b|cosθ | 夹角、垂直判定、投影长度 |
| 叉积 cross | ax·by − ay·bx | |a||b|sinθ（有符号） | 转向、共线、面积 |
| 长度 len | sqrt(dot(a, a)) | |a| | 周长、两点距离 |
| cross(b−a, c−a) | — | 三点转向 / 三角形有向面积 ×2 | 凸包的全部判断 |
本节要新学三样：结构体重载运算符（让自定义类型像 int 一样写）、点积与叉积（两个式子撑起全部几何）、sgn 与 EPS（浮点比较的唯一正确姿势）。
| 组成 | 含义 / 格式要求 |
|---|---|
struct Vec { double x, y; } | 把「点」和「向量」统一成同一个类型。两点之差是向量，向量还叫点——计算几何里不区分这两个概念，共用一个类型最省事。 |
Vec operator-(const Vec& b) const | 成员函数版重载：编译器把 a - b 翻译成 a.operator-(b)。返回类型写成 Vec，所以 b - a 还能继续参与运算。 |
const Vec& b | const 引用传参：不拷贝，并承诺不修改 b。漏掉 const，对 const 对象调用会编译失败。 |
结尾的 const | 承诺这个函数不修改 *this。漏了它，对 const Vec 调用会报错；写了没有坏处。 |
return {x - b.x, y - b.y}; | 花括号初始化，等价于 Vec{x - b.x, y - b.y}，C++11 起可用。 |
bool operator<(const Vec& b) | 给 sort 用：先比 x，x 相等再比 y。凸包的第一步就是按这个顺序排序，运算符写反整份代码都错。 |
重载与 cmp 只能选一个 | sort(v.begin(), v.end()) 用 operator<，sort(v.begin(), v.end(), cmp) 用 cmp。两处定义不一致 → 凸包结果随机。 |
为什么一定要 operator< | Andrew 算法的正确性依赖「按 x 单调」的顺序。没有这个顺序，扫描时弹出的点可能是该留的。 |
#include <bits/stdc++.h>
using namespace std;
struct Vec {
double x, y;
Vec operator-(const Vec& b) const { return {x - b.x, y - b.y}; }
bool operator<(const Vec& b) const { return x != b.x ? x < b.x : y < b.y; }
};
int main() {
Vec a{3, 4}, b{1, 1};
Vec c = a - b; // (2, 3)
cout << c.x << " " << c.y << "\n";
vector<Vec> v{{2, 1}, {1, 5}, {1, 2}};
sort(v.begin(), v.end()); // 先按 x，再按 y
for (auto p : v) cout << "(" << p.x << "," << p.y << ") ";
// (1,2) (1,5) (2,1)
return 0;
}比较器里不要塞 EPS。写成 fabs(x - b.x) > EPS ? ... : ... 会破坏严格弱序，libstdc++ 的 sort 在极端数据上可能越界 → RE。要判浮点相等，用 sgn 写在算法里，别放进比较器。
二元减法是 operator-；一元负号是 operator-()（无参）。两者能共存，别写混。
| 组成 | 含义 / 格式要求 |
|---|---|
dot 的符号 | > 0 锐角，= 0 垂直，< 0 钝角。判垂直就用它，因为 dot = 0 恰好等价于垂直。 |
dot(a, a) | 等于 |a|²。开根号才得到长度：sqrt(dot(a, a))。 |
cross 的符号 | > 0：b 在 a 的逆时针一侧（左转）；< 0：顺时针一侧（右转）；= 0：共线（同向或反向）。凸包的全部判断都是这一句。 |
三点转向 | cross(b - a, c - a) 判断「沿 a→b 走到 c，是左拐还是右拐」。左拐为正、右拐为负、共线为 0。注意两个向量都从同一个点出发。 |
cross 的绝对值 | 等于以 a、b 为邻边的平行四边形面积。三角形 abc 的面积 = fabs(cross(b - a, c - a)) / 2。 |
反对称 | cross(a, b) = -cross(b, a)，所以「转向」带正负号；dot(a, b) = dot(b, a)，所以「夹角」没有方向。 |
量级 | 坐标到 10⁶ 时叉积到 10¹²，int 必炸。整数坐标用 long long，实数坐标用 double。 |
Vec A{0, 0}, B{2, 0}, C{1, 1};
double s = cross(B - A, C - A); // 2*1 - 0*1 = 2 > 0，A->B->C 是左转
cout << s << "\n"; // 2
cout << fabs(s) / 2 << "\n"; // 1：三角形面积
cout << dot(Vec{1, 0}, Vec{0, 1}) << "\n"; // 0：垂直
cout << dot(Vec{1, 0}, Vec{1, 1}) << "\n"; // 1 > 0：锐角两个式子都是「两次乘法、一次加减」，几乎不要钱。看到角度、旋转、面积、方向，先想这两个。
cross 的顺序不能换：ax·by − ay·bx。手滑写成 ax·bx − ay·by 就是点积，程序照跑，结果全错。
| 组成 | 含义 / 格式要求 |
|---|---|
为什么不写 x > 0 | double 用二进制存十进制小数，0.1 存不准。叉积是「两个乘积相减」，两个 10¹² 量级的数相减会带上量级 10⁻⁴ 的误差。直接拿 0 当分界，会把共线判成左转。 |
EPS 取多大 | 跟着数量级走。坐标 ≤ 10⁶ 时叉积 ≤ 10¹²，double 的 53 位尾数只给 15~16 位有效数字，绝对误差约 10⁻⁴。所以本题用 1e-9 其实等于「几乎没有容差」——够用，因为它只影响共线点的取舍。 |
什么时候必须放大 | 做「凸包顶点个数」「点是否在多边形内」这类数量敏感的题，EPS 得按坐标量级放大，否则边界点会随机判错。 |
永远不写 a == b | 浮点判等一律写 sgn(a - b) == 0。 |
输出 | 题目要求几位就输出几位：printf("%.2f\n", ans)。不要手写 round，四舍五入交给 printf。 |
能避开就避开 | 本题坐标最多两位小数，把输入 ×100 存成 long long 后叉积完全精确。这是计算几何最省心的一招：能用整数就绝不用浮点。 |
#include <bits/stdc++.h>
using namespace std;
const double EPS = 1e-9;
int sgn(double x) { return x > EPS ? 1 : (x < -EPS ? -1 : 0); }
int main() {
printf("%d\n", sgn(1e-11)); // 0：当作零
printf("%d\n", sgn(-3.0)); // -1
printf("%d\n", sgn(2.0)); // 1
double a = 0.1 + 0.2;
printf("%d\n", a == 0.3); // 0：不相等
printf("%d\n", sgn(a - 0.3) == 0); // 1：容差内相等
return 0;
}EPS 不是越小越好，也不是越大越好。经验值：坐标 ≤ 10³ 用 1e-9；坐标到 10⁶ 时 1e-9 已经小到没有容差，该按「判的是量级还是个数」来定。
本题有个好处：判错只会让一个近乎共线的点留下或去掉，周长几乎不变。换成「凸包上有几个点」，同样的错判就直接 WA。
凸包是最基础的几何结构：包住所有点的最小凸多边形。它只有一道模板题，但里面每一行都在复用上面三个工具。
农夫约翰要造一圈围栏，把奶牛喜欢吃草的所有地点都围进去，并且要最短。给定这些地点的坐标，求围栏的长度——也就是这些点的凸包周长。
输入格式：第一行一个整数 n，表示放牧点数目；第 2 到第 n+1 行，每行两个实数 xᵢ、yᵢ，表示第 i 个点的坐标。
输出格式：一行一个实数，四舍五入保留两位小数，表示围栏长度。
数据范围：3 ≤ n ≤ 10⁵，−10⁶ ≤ xᵢ, yᵢ ≤ 10⁶，坐标小数点后最多两位。
凸包是什么。包住所有点的最小凸多边形。所有点要么在它内部，要么在它边界上。求周长就是把这个多边形的边长加起来。
先排序。把所有点按 (x, y) 字典序排好。最左和最右的点一定在凸包上。于是凸包被这两个点切成上下两条链，每条链都是从最左走到最右的单调折线。
下链怎么走。从左往右依次加点，用单调栈维护当前的下链。新点 c 加入时，检查「栈顶 b、栈顶之前一个 a」组成的三点转向 cross(b−a, c−b)：如果是右转或共线（≤ 0），说明 b 被包进 a、c 里了，永远当不了凸包顶点，弹掉；反复弹到出现左转，再压入 c。
上链同理。从右往左再扫一遍，沿路同样只保留左转。两段拼起来就是完整凸包。
弹出条件为什么是 ≤ 0 而不是 < 0。取 ≤ 0 会连共线点一起弹掉，得到的是「没有多余顶点」的凸包；取 < 0 会把共线点留在链上。两者在本题等价——多点共线时那些点在同一条边上，边长的和不变。做题要看清楚考的是周长（无害）还是顶点个数（有害）。
为什么弹掉不会错。设栈顶是 b、前一个是 a、新点是 c，且 cross(b−a, c−b) ≤ 0，则 b 在 a→c 这条有向直线的右侧或线上。三角形 a、b、c 里 b 是「凹进去」的那个角，任何包含 a、c 的凸集都不会把 b 当顶点。后面加入的点都在 c 右边，b 就更没机会了。
注意 m > k。下链扫完得到 k 个点，上链的弹出条件必须是 m > k 而不是 m >= 2——否则上链会把下链刚建好的点弹光，凸包退化成两个点。这是整个算法唯一容易写错的地方。
最后一步 --m。上链一路扫到最左点，它的值和起点重复，所以数组末尾多了一个起点。去掉它，剩下的 m 个点就是凸包顶点（逆时针）。
复杂度。排序 O(n log n)，两次扫描各 O(n)（每个点最多进栈一次、出栈一次）。n = 10⁵ 时总操作约 10⁶。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const double EPS = 1e-9;
struct Vec {
double x, y;
Vec operator-(const Vec& b) const { return {x - b.x, y - b.y}; }
bool operator<(const Vec& b) const { return x != b.x ? x < b.x : y < b.y; }
};
int n;
Vec p[N], h[N];
double cross(Vec a, Vec b) { return a.x * b.y - a.y * b.x; }
double dot(Vec a, Vec b) { return a.x * b.x + a.y * b.y; }
double len(Vec a) { return sqrt(dot(a, a)); }
int sgn(double x) { return x > EPS ? 1 : (x < -EPS ? -1 : 0); }
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%lf%lf", &p[i].x, &p[i].y);
sort(p, p + n); // 凸包第一步：按 x 再按 y
int m = 0;
for (int i = 0; i < n; ++i) { // 下链：从左到右，只留左转
while (m >= 2 && sgn(cross(h[m - 1] - h[m - 2], p[i] - h[m - 1])) <= 0) --m;
h[m++] = p[i];
}
int k = m; // 下链的点数，上链不能把它们弹掉
for (int i = n - 2; i >= 0; --i) { // 上链：从右到左
while (m > k && sgn(cross(h[m - 1] - h[m - 2], p[i] - h[m - 1])) <= 0) --m;
h[m++] = p[i];
}
--m; // 末尾与起点重复，去掉
double ans = 0;
for (int i = 0; i < m; ++i)
ans += len(h[(i + 1) % m] - h[i]); // 首尾相连，最后一条边要绕回去
printf("%.2f\n", ans);
return 0;
}| 代码片段 | 含义与理由 |
|---|---|
struct Vec | 点和向量共用一个类型。后面所有 h[i] - h[j] 都是在求向量。 |
sort(p, p + n) | 依赖 operator<。排好序后「从左到右」才有意义，弹出逻辑才成立。 |
while (m >= 2 && ...) | m ≥ 2 才够组成三点转向。不足两点时无条件压栈。 |
cross(h[m-1] - h[m-2], p[i] - h[m-1]) | 三点的转向：从 h[m−2]→h[m−1] 转到 h[m−1]→p[i]。第一个向量是「上一段」，第二个是「新一段」。 |
sgn(...) <= 0 | 右转或共线 → 栈顶是凹点，弹掉。注意是 ≤ 0 而不是 < 0，差一个等号决定共线点留不留。 |
h[m++] = p[i] | 当前点入栈。每个点都会被压一次，最多被弹一次，所以总操作 O(n)。 |
int k = m; | 记下下链长度。上链从这里往上长，弹出条件换成 m > k，保护下链成果。 |
for (int i = n - 2; i >= 0; --i) | 从倒数第二个点往回扫到第 0 个。n−1 已经在下链末尾，不用重复加。 |
--m; | 上链最后压进去的是最左点，与 h[0] 重复。去掉它，h[0..m−1] 才是凸包顶点。 |
h[(i + 1) % m] | 取模实现首尾相连：最后一条边从 h[m−1] 回到 h[0]。 |
len(h[(i+1)%m] - h[i]) | 两点距离 = 差向量的模。整份代码只在这里出现一次根号。 |
一、面积。顶点是逆时针给出的，把每个顶点当成从原点出发的向量，Σ cross(h[i], h[i+1]) 就是面积的 2 倍（鞋带公式）。这条式子和 P1183 的解法是同一个东西。
二、判断点在不在凸包里。逆时针凸包有个漂亮的等价条件：内部就是每条边的左侧交集。逐边判叉积，全部 ≥ 0 就在里面。O(m) 判一次；要更快可以按极角二分，O(log m)。
三、极角排序。Graham 扫描需要按极角排序。用 atan2 能排但慢且不准，标准做法是「先按半平面分组，组内用叉积定先后」，全部整数运算。
double area(Vec* h, int m) { // 顶点逆时针 → 结果为正
double s = 0;
for (int i = 0; i < m; ++i) s += cross(h[i], h[(i + 1) % m]);
return s / 2;
}
bool inHull(Vec q, Vec* h, int m) { // 点在凸包内（含边界），O(m)
for (int i = 0; i < m; ++i)
if (sgn(cross(h[(i + 1) % m] - h[i], q - h[i])) < 0) return false;
return true; // 每条边都不在右侧 → 在里面
}
int half(Vec a) { // 极角排序：上半平面 0，下半平面 1
return (a.y > 0 || (a.y == 0 && a.x > 0)) ? 0 : 1;
}
bool cmpPolar(Vec a, Vec b) { // 极角从小到大
if (half(a) != half(b)) return half(a) < half(b);
return cross(a, b) > 0; // 同一半平面内用叉积定先后
}| 代码片段 | 含义与理由 |
|---|---|
cross(h[i], h[(i+1)%m]) | 两个位置向量直接做叉积 = 三角形 O、h[i]、h[i+1] 的有向面积 ×2。全部加起来，原点在外的部分正负抵消，剩下的正好是多边形面积 ×2。 |
return s / 2 | 上式给的是 2 倍面积。逆时针时为正，顺时针为负，需要绝对值就加 fabs。 |
cross(h[(i+1)%m] - h[i], q - h[i]) | 边向量 与 「边起点指向 q」的向量。叉积为正 = q 在这条边左侧。所有边都满足，q 就在凸包内。 |
< 0 就 return false | 只要有一条边把 q 判在右侧，q 一定在外面——凸包是凸的，方向性是整体一致的。 |
half(a) | 把平面按 x 轴正方向切成两半，先排上半、再排下半，避免 atan2 的精度与常数。 |
cross(a, b) > 0 | 同一半平面内，叉积为正说明 a 的极角小于 b 的极角，a 排在前面。 |
注意 inHull 的 EPS。凸包边长可能很小，叉积量级跟着坐标走。用它判题之前，先按坐标范围把 EPS 调到合适大小，别照抄 1e-9。
上链的弹出条件写成 m >= 2（漏了 m > k）→ 上链会把下链的点全部弹回去，凸包退化成两点一线 → WA，而且样例有时还能过。
叉积写成 a.x * b.x - a.y * b.y（把 by 打成 bx）→ 那是点积的式子，程序照跑，结果完全不对 → WA。编译期间发现不了，只能靠手算一个三角形验证。
弹出条件写成 < 0 而不是 <= 0：共线点会留在凸包里。本题只求周长，留着不影响答案；换成「凸包面积」「凸包顶点数」就会出事。
数组开小。h 的长度会涨到 n+1（凸包最多 n 个顶点，末尾再加一个与起点重复的点），所以 p、h 都要开到 10⁵+5 以上。只开 10⁵ → 越界 RE。
在比较器里塞 EPS（fabs(x - b.x) > EPS）破坏严格弱序 → sort 越界 RE，或者顺序乱掉 WA。
用 int 读实数坐标：只读到整数部分，小数被丢掉 → WA，而样例恰好都是整数时完全看不出来。必须 double + scanf("%lf")。
所有点共线时 --m 之后 m = 2，周长 = 2 × 两端距离。看着像「算错了一倍」，其实是对的——退化凸包就是一条线段，来回各走一遍。想要别的约定就得特判。
关掉页面，把 P2742 的 40 行从零敲一遍，提交确认样例输出 14.00。
改一改①：把上链的 m > k 改成 m >= 2，先预测再跑。结果是 12.00 而不是 14.00——上链把角点 (4,3) 弹掉了，凸包变成一个缺角的三角形。
改一改②：在 --m 后面加一句 cout << m << "\n";，对样例（6 个点，2 个在内部）应该看到 4。再把 <= 0 改成 < 0，喂 5 个共线的点 (0,0)(1,0)(2,0)(3,0)(4,0) 进去：m 从 2 变成 8（正着数一遍、反着再数一遍），而周长仍然是 8.00 —— 顶点数变了，答案没变。
改一改③：把 sort(p, p + n); 注释掉，用同一组数据多跑几次，观察结果乱跳——这是「顺序决定正确性」最直观的现场。
改一改④：把 scanf("%d", &n) 之后的读入改成 cin >> p[i].x，然后关掉 sync_with_stdio，对比一下 10⁵ 个点的运行时间。
把叉积写成行列式：cross(a, b) = ax·by − ay·bx = |ax ay; bx by|。行列式的绝对值等于以这两个向量为邻边的平行四边形面积，所以叉积的绝对值就是面积，而它的正负号由「b 在 a 的左边还是右边」决定。
由 a·b = |a||b|cosθ、a×b = |a||b|sinθ 两式之比可得 tanθ = cross/dot。这就是为什么「判角度」用点积、「判方向」用叉积：cos 是偶函数，分不清左右；sin 是奇函数，能分。
三点转向。取 u = b − a、v = c − a，则 cross(u, v) = |u||v|sin∠bac。sin 在 (0, π) 上为正、(π, 2π) 上为负，正好对应「c 在 a→b 左侧 / 右侧」。共线时 sin = 0。
鞋带公式怎么来。把多边形每条边 PᵢPᵢ₊₁ 和原点 O 连成三角形，有向面积 cross(Pᵢ, Pᵢ₊₁)/2 全部相加。原点在多边形外部时，有些三角形是「负」的，它们的重叠部分恰好正负抵消，总和仍然等于多边形面积。这就是为什么它对任意位置的坐标系都成立，不需要把原点搬进多边形。
叉积的双线性。cross(a, b + c) = cross(a, b) + cross(a, c)，cross(ka, b) = k·cross(a, b)。鞋带公式能一项项拆开累加，靠的就是这个性质。点积同样双线性，所以内积空间那套线性代数在这里全部通用。
整数坐标的面积。坐标全是整数时，Σ(xᵢyᵢ₊₁ − xᵢ₊₁yᵢ) 是整数，所以多边形面积一定是整数或半整数。P1183 保证面积是整数，于是这个和一定是偶数，s / 2 用整数除法不会丢精度。这是「整数几何」的核心事实，也是为什么能用 long long 全程避开浮点。
精度从哪来。double 有 53 位尾数，约 15.9 位十进制有效数字。坐标 ≤ 10⁶ 时叉积 ≤ 2×10¹²，此时 1 ulp ≈ 2×10¹² / 9×10¹⁵ ≈ 2×10⁻⁴。所以在这种量级下，1e-9 的 EPS 实际上不起任何作用；真要容差就得取 10⁻³ 甚至更大，但那会让「确实很小的左转」被判成共线。想让判断可靠，正确做法是把坐标缩放到整数，而不是调 EPS。
--m 之后 m 等于几？周长输出多少？把这个值和「线段长度」比一比，解释为什么是两倍。cross((2,0), (1,1)) 的符号，并说出 A(0,0)、B(2,0)、C(1,1) 这三点的转向。m > k 的作用，以及漏掉它会退化成什么形状。--m 在删哪个点，不删会导致什么后果。给出一个没有缺口的简单多边形，它的每条边都平行于坐标轴之一。顶点按逆时针方向逐个给出，坐标都是整数，因此面积也是整数。注意可能存在连续三个顶点共线。
求这个多边形的面积。
输入格式：第一行一个整数 n，表示顶点数；接下来 n 行，每行两个整数 x、y，表示一个顶点。多边形最后由最后一个顶点连回第一个顶点封闭。
输出格式：一行一个整数，表示面积。数据范围：1 ≤ n ≤ 100，−200 ≤ x, y ≤ 200。
顶点是逆时针给的，这个顺序本身就是信息。想想「每条边和原点组成的三角形，有向面积加起来」会得到什么。
三角形 OAB 的有向面积 = cross(A, B) / 2，其中 cross(A, B) = Ax·By − Ay·Bx。把它对每条边累加。
累加出来的和是面积的两倍，一定是偶数。所以最后再做一次除以 2，过程中不要提前除。
这是鞋带公式（Shoelace Formula）最直接的用法：S = |Σ (xᵢ·yᵢ₊₁ − xᵢ₊₁·yᵢ)| / 2，下标 i+1 对 n 取模，保证最后一条边连回首点。
为什么对。对每条边 PᵢPᵢ₊₁，xᵢyᵢ₊₁ − xᵢ₊₁yᵢ 正好是 cross(Pᵢ, Pᵢ₊₁)，等于三角形 O、Pᵢ、Pᵢ₊₁ 的有向面积的两倍。把 n 个三角形加起来，落在多边形外面的部分正负抵消，剩下的正好是多边形本身，所以总和 = 2S。这与原点在不在多边形内部无关。
方向的处理。逆时针给出时每一项的累加结果为正，直接取用即可。加一句 if (s < 0) s = -s; 更保险：万一题目给的顺序反了，也不会输出负数。
为什么最后才除以 2。过程中每一项都是整数，累加也是整数，只有最后一步可能是「半个」。本题保证面积是整数，所以总和一定是偶数，整数除法不会丢精度。若提前做除法，就会引入 .5 甚至浮点误差。
共线顶点怎么办。不用管。三个点共线时，对应的两个三角形有向面积恰好相互抵消（或其中一个为 0），总和不变。这也是为什么题目特意提示「可能存在连续三个顶点共线」——它在提醒你不要去做去重。
规模。n ≤ 100、坐标 ≤ 200，|s| ≤ 100 × 2 × 200 × 200 = 8×10⁶，int 就够；但养成习惯用 long long，坐标范围稍微大一点（10⁹）就会溢出。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> x(n), y(n);
for (int i = 0; i < n; ++i) cin >> x[i] >> y[i];
long long s = 0; // 有向面积的两倍，一定是偶数
for (int i = 0; i < n; ++i) {
int j = (i + 1) % n; // 最后一条边：末点连回首点
s += x[i] * y[j] - x[j] * y[i]; // 就是 cross(P_i, P_j)
}
if (s < 0) s = -s; // 万一是顺时针给出，取绝对值
cout << s / 2 << "\n"; // 整数除法，答案必为整数
return 0;
}| 片段 | 作用 |
|---|---|
vector<long long> x(n), y(n) | 把所有点先全部读进来。首尾成环，必须在算之前知道全部坐标。 |
int j = (i + 1) % n | 取模实现闭环。i = n−1 时 j = 0，最后一条边自动连回起点。 |
x[i] * y[j] - x[j] * y[i] | 叉积 cross(P_i, P_j) 的展开，也就是三角形 O、Pᵢ、Pⱼ 的有向面积的两倍。顺序不能反，反了整体变号。 |
s += ... | 把所有有向面积累加。多边形外侧的三角形贡献负值，抵消后剩下 2S。 |
if (s < 0) s = -s; | 逆时针时 s 本就为正；加这一句是为了防止题目顺序与预期不符。 |
cout << s / 2 | 最后一步才除。本题保证面积为整数，所以 s 必为偶数，整数除法精确。 |
s += (x[i]*y[j] - x[j]*y[i]) / 2，每项都截断，答案差一大截。i < n-1）→ 少了「末点连回首点」那一块，WA。x[i]*x[j] - y[i]*y[j]（点积的形式）→ 完全不对，但照样能跑。