数学：坐标系内叉乘求多边形面积减少误差——Cake

Attempted 20 / 137 C Gym 100753C Cake

其实这是一道简单题，
关键在于数学公式和误差缩小

题意：
凸多边形蛋糕太大了，要切为原来的a倍，按每个边的1/s处切，
输出s，保证2 ≤ s ≤ 1000 ，允许10^?4的误差

输入
0.875（剩余比例） 4（顶点数）
0 0（各顶点坐标）
8 0
8 4
0 4

后来补题终于ac了，ac代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define fab(a) a>0?a:-a
#define mem(a,b) memset(a,b,sizeof(a))
#define N 105
struct node{
    double x,y;
}a[N];
int n;
inline double sq(double x1,double y1,double x2,double y2){
    //printf("%f\n",(x1*y2-x2*y1)/2);return (x1*y2-x2*y1)/2;
}
inline int lop(int i){
    return (i+n-1)%n+1;
}
int main()
{
    FILE*fp=stdin;//fopen("text.in","r");//记得注释stdin;//double rate;//输入 fscanf(fp,"%lf%d",&rate,&n);for(int i=1;i<=n;i++){
    fscanf(fp,"%lf%lf",&a[i].x,&a[i].y);}//求总面积,减少面积 double s=0;for(int i=1;i<=n;i++){
    s+=sq(a[lop(i)].x,a[lop(i)].y,a[lop(i+1)].x,a[lop(i+1)].y);} double ds=fab(s*(1-rate));//printf("ds=%f\n",ds);//对m二分,m为s double l=2,r=1000;double m=(l+r)/2;double sum=0;for(int i=1;i<=n;i++){
    sum+=fab(sq((a[lop(i)].x-a[lop(i-1)].x),(a[lop(i)].y-a[lop(i-1)].y),(a[lop(i)].x-a[lop(i+1)].x),(a[lop(i)].y-a[lop(i+1)].y)));//每次sumn+=fab(sq((a[lop(i)].x-a[lop(i-1)].x)/m,(a[lop(i)].y-a[lop(i-1)].y)/m,(a[lop(i)].x-a[lop(i+1)].x)/m,(a[lop(i)].y-a[lop(i+1)].y)/m));//是错的，由于浮点数误差！4.47算成4.59，且每次sumn都有一点误差//还有一个，975.900073算成975.900070，已经显现出卡浮点数误差的迹象了//所以计算尽量想办法只总除一次。 }while((r-l)>=1e-6){
    m=(l+r)/2;double sumn=sum/m/m;//printf("m=%8f sum=%8f\n",m,sumn);//if(sumn>=ds){
    l=m+1e-6;}else{
    r=m-1e-6;}}printf("%f\n",m);return 0;
}

方法技巧：

数学：坐标系内求多边形面积

s=1/2*fabs((x[1]*y[2]-x[2]*y[1])+(x[2]*y[3]-x[3]*y[2])+...
... +(X[k]*Y[k+1]-X[k+1]*Y[k])+...+(X[n]*y[1]-x[1]*Y[n]) )
// <stdlib.h>下有 int abs(int x) ，绝对值函数但是只对整数有用。
// <math.h>下有double fabs(double x) ，对浮点数有用

理解上，是叉乘，且分正负
如图：

误差处理

1，二分法，要有一个eps，防止浮点数误差
2，多想一下。
根据相似面积关系，可以先算出在1/2处切割的面积总和S。
再二分b时，是S/b²
比每次二分b时算各sum误差小了！
原因，浮点数除多了会有误差，
计算尽量想办法只总除一次。
确实就WA到AC了

附大佬方法(https://blog.csdn.net/qq_51945248/article/details/116244891)