【CodeForces 613A】Peter and Snow Blower
and Codeforces
2023-09-11 14:19:25 时间
题意
给出原点(不是(0,0)那个原点)的坐标和一个多边形的顶点坐标,求多边形绕原点转一圈扫过的面积(每个顶点到原点距离保持不变)。
分析
多边形到原点的最小距离和最大距离构成的两个圆之间的圆环就是所求面积。
判断最大距离一定在顶点上,最小距离可能在点上也可能在边上。
如果原点到一个顶点的连线和它所在的边构成钝角,那么最小距离在点上,否则最小距离就是顶点和该边构成三角形的原点所在的高,可以用海伦公式求三角形面积,然后求高。
不过我用的方法是点到直线的距离公式。
然后π用 acos(-1.0) 表示。
代码
#include <stdio.h> #include<iostream> #include <cmath> #define dd double using namespace std; int n; dd far,nea=1e19,t,P=acos(-1.0); struct po { double x,y; } p[100005]; dd P_P(po a,po b) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } dd P_L(po a,po b,po c)//point c --> line ab { dd l1=P_P(a,b); dd l2=P_P(a,c); dd l3=P_P(b,c); if(l2*l2 >= (l1*l1+l3*l3)) return l3; if(l3*l3>=(l2*l2+l1*l1)) return l2; dd A=a.y-b.y; dd B=b.x-a.x; dd C=a.x*b.y - a.y*b.x; //line ab: Ax+By+C=0; dd D=A*c.x + B*c.y + C; return fabs(D*D/(A*A+B*B)); } int main() { scanf("%d",&n); for(int i=0;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); for(int i=1;i<=n;i++) { if (i<n) nea = min( P_L(p[i], p[i+1], p[0]), nea); else nea = min( P_L(p[n], p[1], p[0]), nea); far=max(far,P_P(p[0],p[i])); } printf("%.18lf\n",P*(far-nea)); return 0; }
相关文章
- How to: View and edit code by using Peek Definition (Alt+F12)
- What is event bubbling and capturing?
- CodeCraft-22 and Codeforces Round #795 (Div. 2) C. Sum of Substrings
- Codeforces Round #779 (Div. 2) B. Marin and Anti-coprime Permutation
- 解决 If you are on Ubuntu or Debian, install libgtk2.0-dev and pkg-config, then re-run cmake or configure script in function 'cvNamedWindow'
- English trip M1 - PC6 Likes and Dislike Teacher:Jade
- CodeForces 221D Little Elephant and Array
- CodeForces 712C Memory and De-Evolution (贪心+暴力)
- CodeForces 289A Polo the Penguin and Segments (水题)
- CodeForces 339C Xenia and Weights(暴力求解DFS)
- CodeForces 339B Xenia and Ringroad(水题模拟)
- CodeForces 342C Cupboard and Balloons (几何问题)
- FFmpeg and x264 Encoding Guide
- swift开发网络篇 - 用户登录POST JSON and header
- 【HDU 5833】Zhu and 772002(异或方程组高斯消元)
- 【CodeForces 611C】New Year and Domino
- Phillip and Trains (dfs做更简单)
- Codeforces Round #226 (Div. 2)--A Bear and Raspberry
- Codeforces Round #250 (Div. 1) D. The Child and Sequence
- Codeforces Round #234 (Div. 2):B. Inna and New Matrix of Candies
- [LeetCode] Bulls and Cows 公母牛游戏