广州现场赛D题Signal Interference(计算几何)

2024-06-01 18:58

本文主要是介绍广州现场赛D题Signal Interference(计算几何),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Signal Interference

题目链接

思路:推推公式就发现其实就是求一个圆和多边形面积的交

代码:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<algorithm>const double eps = 1e-8;
const double pi = acos(-1.0);int dcmp(double x)
{if(x > eps) return 1;return x < -eps ? -1 : 0;
}struct Point
{double x, y;Point(){x = y = 0;}Point(double a, double b){x = a, y = b;}inline void read() {scanf("%lf%lf", &x, &y);}inline Point operator-(const Point &b)const{return Point(x - b.x, y - b.y);}inline Point operator+(const Point &b)const{return Point(x + b.x, y + b.y);}inline Point operator*(const double &b)const{return Point(x * b, y * b);}inline double dot(const Point &b)const{return x * b.x + y * b.y;}inline double cross(const Point &b, const Point &c)const{return (b.x - x) * (c.y - y) - (c.x - x) * (b.y - y);}inline double Dis(const Point &b)const{return sqrt((*this - b).dot(*this - b));}inline bool InLine(const Point &b, const Point &c)const//三点共线{return !dcmp(cross(b, c));}inline bool OnSeg(const Point &b, const Point &c)const//点在线段上,包括端点{return InLine(b, c) && (*this - c).dot(*this - b) < eps;}
};inline double min(double a, double b)
{return a < b ? a : b;}
inline double max(double a, double b)
{return a > b ? a : b;}
inline double Sqr(double x)
{return x * x;}
inline double Sqr(const Point &p)
{return p.dot(p);}Point LineCross(const Point &a, const Point &b, const Point &c, const Point &d)
{double u = a.cross(b, c), v = b.cross(a, d);return Point((c.x * v + d.x * u) / (u + v), (c.y * v + d.y * u) / (u + v));
}double LineCrossCircle(const Point &a, const Point &b, const Point &r, double R, Point &p1, Point &p2)
{Point fp = LineCross(r, Point(r.x + a.y - b.y, r.y + b.x - a.x), a, b);double rtol = r.Dis(fp);double rtos = fp.OnSeg(a, b) ? rtol : min(r.Dis(a), r.Dis(b));double atob = a.Dis(b);double fptoe = sqrt(R * R - rtol * rtol) / atob;if(rtos > R - eps) return rtos;p1 = fp + (a - b) * fptoe;p2 = fp + (b - a) * fptoe;return rtos;
}double SectorArea(const Point &r, const Point &a, const Point &b, double R)
//不大于180度扇形面积,r->a->b逆时针
{double A2 = Sqr(r - a), B2 = Sqr(r - b), C2 = Sqr(a - b);return R * R * acos((A2 + B2 - C2) * 0.5 / sqrt(A2) / sqrt(B2)) * 0.5;
}double TACIA(const Point &r, const Point &a, const Point &b, double R)
//TriangleAndCircleIntersectArea,逆时针,r为圆心
{double adis = r.Dis(a), bdis = r.Dis(b);if(adis < R + eps && bdis < R + eps) return r.cross(a, b) * 0.5;Point ta, tb;if(r.InLine(a, b)) return 0.0;double rtos = LineCrossCircle(a, b, r, R, ta, tb);if(rtos > R - eps) return SectorArea(r, a, b, R);if(adis < R + eps) return r.cross(a, tb) * 0.5 + SectorArea(r, tb, b, R);if(bdis < R + eps) return r.cross(ta, b) * 0.5 + SectorArea(r, a, ta, R);return r.cross(ta, tb) * 0.5 + SectorArea(r, a, ta, R) + SectorArea(r, tb, b, R);
}const int N = 505;Point p[N];double SPICA(int n, Point r, double R)//SimplePolygonIntersectCircleArea
{int i;double res = 0, if_clock_t;for(i = 0; i < n; ++ i){if_clock_t = dcmp(r.cross(p[i], p[(i + 1) % n]));if(if_clock_t < 0) res -= TACIA(r, p[(i + 1) % n], p[i], R);else res += TACIA(r, p[i], p[(i + 1) % n], R);}return fabs(res);
}int n;
double xa, ya, xb, yb, k;int main() {int cas = 0;while (~scanf("%d%lf", &n, &k)) {for (int i = 0; i < n; i++) p[i].read();scanf("%lf%lf%lf%lf", &xa, &ya, &xb, &yb);Point o = Point(-(xb - k * k * xa) / (k * k - 1), -(yb - k * k * ya) / (k * k - 1));double r = (xb * xb + yb * yb - k * k * xa * xa - k * k * ya * ya) / (k * k - 1);r += (o.x * o.x + o.y * o.y);r = sqrt(r);printf("Case %d: %.10lf\n", ++cas, SPICA(n, o, r));}return 0;
}


这篇关于广州现场赛D题Signal Interference(计算几何)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1021844

相关文章

uva 10387 Billiard(简单几何)

题意是一个球从矩形的中点出发,告诉你小球与矩形两条边的碰撞次数与小球回到原点的时间,求小球出发时的角度和小球的速度。 简单的几何问题,小球每与竖边碰撞一次,向右扩展一个相同的矩形;每与横边碰撞一次,向上扩展一个相同的矩形。 可以发现,扩展矩形的路径和在当前矩形中的每一段路径相同,当小球回到出发点时,一条直线的路径刚好经过最后一个扩展矩形的中心点。 最后扩展的路径和横边竖边恰好组成一个直

poj 1113 凸包+简单几何计算

题意: 给N个平面上的点,现在要在离点外L米处建城墙,使得城墙把所有点都包含进去且城墙的长度最短。 解析: 韬哥出的某次训练赛上A出的第一道计算几何,算是大水题吧。 用convexhull算法把凸包求出来,然后加加减减就A了。 计算见下图: 好久没玩画图了啊好开心。 代码: #include <iostream>#include <cstdio>#inclu

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

uva 11178 计算集合模板题

题意: 求三角形行三个角三等分点射线交出的内三角形坐标。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <

XTU 1237 计算几何

题面: Magic Triangle Problem Description: Huangriq is a respectful acmer in ACM team of XTU because he brought the best place in regional contest in history of XTU. Huangriq works in a big compa

poj 3304 几何

题目大意:给出n条线段两个端点的坐标,问所有线段投影到一条直线上,如果这些所有投影至少相交于一点就输出Yes!,否则输出No!。 解题思路:如果存在这样的直线,过投影相交点(或投影相交区域中的点)作直线的垂线,该垂线(也是直线)必定与每条线段相交,问题转化为问是否存在一条直线和所有线段相交。 若存在一条直线与所有线段相交,此时该直线必定经过这些线段的某两个端点,所以枚举任意两个端点即可。

POJ 2318 几何 POJ 2398

给出0 , 1 , 2 ... n 个盒子, 和m个点, 统计每个盒子里面的点的个数。 const double eps = 1e-10 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;}struct Point{double x , y

poj 2653 几何

按顺序给一系列的线段,问最终哪些线段处在顶端(俯视图是完整的)。 const double eps = 1e-10 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;}struct Point{double x , y ;Point(){}Po

音视频入门基础:WAV专题(10)——FFmpeg源码中计算WAV音频文件每个packet的pts、dts的实现

一、引言 从文章《音视频入门基础:WAV专题(6)——通过FFprobe显示WAV音频文件每个数据包的信息》中我们可以知道,通过FFprobe命令可以打印WAV音频文件每个packet(也称为数据包或多媒体包)的信息,这些信息包含该packet的pts、dts: 打印出来的“pts”实际是AVPacket结构体中的成员变量pts,是以AVStream->time_base为单位的显

计算数组的斜率,偏移,R2

模拟Excel中的R2的计算。         public bool fnCheckRear_R2(List<double[]> lRear, int iMinRear, int iMaxRear, ref double dR2)         {             bool bResult = true;             int n = 0;             dou