2025杭电多校第九场乘法逆元、阿斯蒂芬、计算几何个人题解怎么写？
摘要：计算几何 计算几何 题目 思路 由于给定的是一条不自交的折线，因此可以直接沿着给定的折线来走 如果下一个点相对于当前的前进方向是向左，那么当前点标记为1，否则为0 判断方向可以通过相邻的两个线段的向量的叉乘正负性 最后根据给定的折线是顺时针
计算几何
计算几何
题目
思路
由于给定的是一条不自交的折线，因此可以直接沿着给定的折线来走
如果下一个点相对于当前的前进方向是向左，那么当前点标记为1，否则为0
判断方向可以通过相邻的两个线段的向量的叉乘正负性
最后根据给定的折线是顺时针还是逆时针来判断1、0对应的是\(YES,NO\)
如何判断给定的折线是顺时针还是逆时针呢？
可以对相邻的两个点的向量进行叉乘后累加，计算这个多边形的面积，最后判断总面积的正负形就可以知道给定的折线是顺时针还是逆时针了
特别需要注意的是，由于给定的点都是整数，叉乘计算出来的数也是整数，如果用板子里自带的\(double\)类型的变量和函数，将会出现精度问题！！
赛时因为这个问题\(WA\)了8发
代码实现
#include<iostream>
#include<vector>
#include<cmath>
#include<queue>
#include<algorithm>
#include<unordered_map>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(int i = (a); i <= (b); i ++)
#define per(i, a, b) for(int i = (a); i >= (b); i --)
#define see(stl) for(auto&ele:stl)cout<<ele<<" "; cout<<'\n';
constexpr int inf = 1e9 ;
#define double ll
#define int ll
const double eps=1e-6;
const int N=5e5+5;
const double pi=acos(1.0*-1);
struct Vector {
double x, y;
Vector():x(0),y(0){}
Vector(double a, double b) :x(a), y(b) {}
bool operator<(const Vector&t)const{
if(x!=t.x)return x<t.x;
return y<t.y;
}
};
struct node{
Vector v;
int pd;
bool operator<(const node&t)const{
return v<t.v;
}
}a[N];
Vector operator+(Vector a, Vector b) {
return Vector(a.x + b.x, a.y + b.y);
}
Vector operator-(Vector a, Vector b) {
return Vector(a.x - b.x, a.y - b.y);
}
double operator*(Vector a, Vector b) {
return a.x * b.y - a.y * b.x;
}
double cross(Vector a, Vector b, Vector c) {
return (b - a) * (c - a);
}
double operator&(Vector a, Vector b) {
return a.x * b.x + a.y * b.y;
}
double dot(Vector a, Vector b, Vector c) {
return (b - a) & (c - a);
}
void eachT() {
int n;cin>>n;
int cnt=0;
rep(i,1,n){
cin>>a[i].v.x>>a[i].v.y;
}
Vector v=a[n].v-a[n-1].v;
Vector last=a[n].v;
int S=0;
rep(i,1,n){
Vector p,now;
S+=a[i].v*a[(i-1-1+n)%n+1].v;
p=a[i].v;
now=p-last;