锐客网

  1. 首页 > it技术 > >

51Nod-1976-多边形划分

题目链接：点击打开链接
（一）题面：
1976 多边形划分


给一个共有 n个点的凸多边形，求一条将该多边形划分为面积和周长都相等的两部分 的直线。
Input

第一行一个正整数n，表示多边形的点数。（n <= 40000） 接下来的n行,第i+1行，每行两个实数xi,yi,表示凸多边形的一个点的坐标，点按照逆时针或顺时针的顺序给出。 其中n，|xi|,|yi|<=40000。

Output
如果存在这样的直线，将这条直线与凸多边形的两个交点的坐标分两行输出。你所求的直线必须与多边形有两个交点，且分多边形的两部分周长或面积相差都不能大于10^-3。 如果不存在，输出"impossible"（不含引号）。

Input示例
4 0 0 3 0 3 3 0 3

Output示例
1 0 2 3



（二）题目大意：
见题面QAQ.



（三）解题思路：
像我这么菜当然是没想到思路的啦~...
【51Nod-1976-多边形划分】下面是官方题解：

①首先，我们对这条直线的存在性进行证明。
在凸多边形上任取一点P ，定义函数 f(x) ：设凸多边形周长为 C，从 P 点出发在凸多边形上沿顺时
针方向移动 x 个单位长度后，设到达的点为Q1，从P+C/2点出发沿着凸多边形移动x个单位长度后到达 Q2
，函数值为射线 Q1Q2 两侧的面积差。不难发现有 f(x)=?f(x+C2) ，因为此时射线刚好翻转。根据零点存

在定理可知在区间 [0,C2]存在一实数 x0 使得 f(x0)=0 ，证毕。
② 存在性得到证明后，只需求解出函数的一个零点即可。可采用二分法求出零点。显然零点可能并不一定唯
一，但我们只需求出一个零点，二分法仍然适用，只需在缩小区间的时候保证区间内一定存在一个零点即可
（设当前考虑的区间为[l,r]，只需保证f(l)与f(r)异号）。至此算法便水落石出了。
③算法的时间复杂度为 O(nlogC)。
其图示如下：

51Nod-1976-多边形划分
文章图片


设：F(x)=S1-S2，则F(x+C/2)=S2-S1，又因为F(x)是连续的，所以有了题解中的结论，然后二分求零点即

可。
（四）具体代码：
#include #include #include #include #include #include #define id (SP+1)%n using namespace std; const int maxn=4e4+10; struct Point{ double x,y; Point(){} Point(double _x,double _y){ x=_x; y=_y; } }P[maxn]; double dist(Point A,Point B){ return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)); } double Area(Point A,Point B,Point C){//三角形面积 double x1=B.x-A.x,y1=B.y-A.y; double x2=C.x-A.x,y2=C.y-A.y; return fabs(x1*y2-x2*y1)/2.0; } const double esp=1e-9; Point getp(Point A,Point B,double x){//求线段AB上距离A点x长度的点 double d=dist(A,B); double ex=(B.x-A.x)/d; double ey=(B.y-A.y)/d; double _x=A.x+ex*x; double _y=A.y+ey*x; return Point(_x,_y); } double fx(double x,double c,double s,int n){//求F(x) int SP=0; double d; while((d=dist(P[SP],P[id]))

（五）总结一下：
①计算几何往往需要去寻找一些重要的数学关系。

②这里被卡了精度，真是#￥%……&*，我那里二分判断的条件貌似不是很“标准”，然后输出小数的位数

要够多，貌似计算几何问题里面涉及到精度的问题还不少...。
③照着题解的思路写，代码写得比较难看...有待改进。

    推荐阅读


    上一篇：angularjs2 路由之传参

    下一篇：CSS+DIV网页样式与布局——文字样式&段落（一）