前提提要：向量叉积以后改用 ^ 符号，重载运算符后发现表示更清晰。
friend double operator ^ (Point a,Point b){
return a.x*b.y-a.y*b.x;
} 三角形面积的计算。
1.解析几何法：由众多三角形的面积公式得出的结果：
2.向量叉积法：任意两边向量的叉积的绝对值的1/2即为三角形的面积。
Code：
double TriangleArea(V l1,V l2){
return fabs((l1.end-l1.start)^(l2.end-l2.start))/2;
} 多边形面积的计算。
现在讨论简单多边形，不考虑自交多边形，计算时采用剖分思想，将其转化为求多个三角形面积的子问题集合。
有三种转化方法：
1.将多边形内的一点与多边形顶点连线，可将多边形划分成多个三角形，分别求出每个三角形的面积，累加起来即为多边形的面积。
2.采用三角剖分的方法，取多边形的一个顶点作为剖分出的三角形顶点，三角形的其他点作为多边形上相邻的点，
由于叉乘有正有负，所以正好可以抵消掉多余的面积部分。面积的计算公式为：
计算得到的面积都一样。
Code：
//简单多边形面积，由n个点构成Dots顶点集，按顺序存储。
double Poly_Area(){
double ans=0;
for(int i=1;i<n;++i){
ans+=(Dots[i]-Dots[0])^(Dots[i+1]-Dots[0]);
}return fabs(ans)/2.0;
} 若所取得的点不在多边形内，也不是多边形的顶点，而是原点时，多边形的面积公式也可以写成：
S△=1/2sigam（xi*y(i+1) - x(i+1)*yi）；
Code：
//简单多边形的面积，Dots[]为顶点集，n为多边形的顶点个数。
double Poly_Area2(){
Dots[n]=Dots[0];
double ans=0;
for(int i=0;i<n;++i){
ans+=(Dots[i])^(Dots[i+1]);
}return fabs(ans)/2.0;
} 照例进行OJ测试：
牛客练习赛36-F：https://ac.nowcoder.com/acm/contest/328/F
前缀和+多边形面积。
ACCode：
// luogu-judger-enable-o2
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<math.h>
//#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define Pair pair<int,int>
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// 水印
//std::ios::sync_with_stdio(false);
// register
const int MAXN=1e5+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const int MOD=998244353;
const double PI=acos(-1.0);
const double EPS=1.0e-12;
struct Point{
double x,y;
Point(double _x=0,double _y=0){
x=_x;y=_y;
}
friend Point operator + (const Point &a,const Point &b){
return Point(a.x+b.x,a.y+b.y);
}
friend Point operator - (const Point &a,const Point &b){
return Point(a.x-b.x,a.y-b.y);
}
friend double operator ^ (Point a,Point b){
return a.x*b.y-a.y*b.x;
}
}Dots[MAXN];
struct V{
Point start,end;double ang;
V(Point _start=Point(0,0),Point _end=Point(0,0),double _ang=0.0){
start=_start;end=_end;ang=_ang;
}
friend V operator + (const V &a,const V &b){
return V(a.start+b.start,a.end+b.end);
}
friend V operator - (const V &a,const V &b){
return V(a.start-b.start,a.end-b.end);
}
}Edge[MAXN],stk[MAXN];
double Seare[MAXN];
int n;
int Parellel(const V &a,const V &b){
return fabs((a.end-a.start)^(b.end-b.start))<EPS;
}
Point LineInterDot(const V &l1,const V &l2){
Point p;
double S1=(l2.end-l1.start)^(l2.start-l1.start);
double S2=(l2.start-l1.end)^(l2.start-l1.start);
p.x=(l1.start.x*S2+l1.end.x*S1)/(S1+S2);
p.y=(l1.start.y*S2+l1.end.y*S1)/(S1+S2);
return p;
}
double TriangleArea(V l1,V l2){
return fabs((l1.end-l1.start)^(l2.end-l2.start))/2;
}
double Poly_Area(){
double ans=0;
for(int i=1;i<n;++i){
ans+=(Dots[i]-Dots[0])^(Dots[i+1]-Dots[0]);
}return fabs(ans)/2.0;
}
double Poly_Area2(){
Dots[n]=Dots[0];
double ans=0;
for(int i=0;i<n;++i){
ans+=(Dots[i])^(Dots[i+1]);
}return fabs(ans)/2.0;
}
int main(){
int n,q;cin>>n>>q;
for(int i=1;i<=n;++i){
cin>>Dots[i].x>>Dots[i].y;
}
for(int i=1;i<n;++i){
Seare[i]=Seare[i-1]+((Dots[i]-Dots[1])^(Dots[i+1]-Dots[1]))/2.0;
}double sum=Seare[n-1],ans=0;
// for(int i=1;i<n;++i){
// cout<<Seare[i]<<" ";
// }cout<<endl;
while(q--){
int a,b;double res=0;
cin>>a>>b;
if(a>b) swap(a,b);
if(a+1==b) continue;
res=Seare[b-1]-Seare[a-1];
res-=((Dots[a]-Dots[1])^(Dots[b]-Dots[1]))/2;
ans=max(ans,min(res,sum-res));
}cout<<ans<<endl;
}
/*
4 2
0.5 0.5
10.5 0.5
10.5 10.5
0.5 10.5
1 3
4 2
*/
京公网安备 11010502036488号