ZOJ1675矩形与圆的面积交

作者：停留的烟蒂_984 | 来源：互联网 | 2023-10-10 13:48

LittleMammothTimeLimit:5Seconds MemoryLimit:32768KB SpecialJudgeItiswellkn

Little Mammoth

Time Limit: 5 Seconds Memory Limit: 32768 KB Special Judge

It is well known that mammoths used to live in caves. This is a story of a little mammoth who lived in a cave with his mummy and daddy.

The mammoth was little and very cute. And he was very curious.He used to peep out of the cave and look around. And one day mummysaid him:

“You are a big boy now, dear, so you may go out of thecave and take a little small walk around. But beware! There isa lot of danger outside. Horrible humans may try to catch youand make a dinner out of you! Do no walk further than r metersaway from the cave entrance.”

And the little mammoth made the first step out of the cave. He wasa good boy, so he decided not to violate mummy‘s order. Butsuddenly he saw a nice field of grass around. Nice, green,juicy, tasty grass! How could he stand it!

But no, those dangerous humans. Little mammoth thought for a whileand decided that he would only eat the grass that he can reachnot breaking mummy‘s recommendation.

The field of grass is a rectangle. Find out how much grass canlittle mammoth eat.

Input

There are several test cases in the input. The first line of each case contains x_c , y_c and r ---coordinates of the entrance to the cave and the distance littlemammoth is allowed to walk from it.

Next line contains x₁ , y₁ , x₂ , and y₂ --- coordinatesof two opposite corners of the grass field. Coordinate systemis set up in such a way that field‘s sides are parallel to coordinate axes.

All numbers in the input file are integer and do not exceed 1000by their absolute values, r > 0, both field sides are non-zero.

There is an empty new line between each case.

Output

Output the area of the part of the field where little mammoth can eat grass. Your answer must be accurate up to 10^-6.
There should be an empty new line between each case.

Example

Input	Output
0 0 5 3 3 7 7	0.547426365104

模板有bug，找了一天，终于找到了，对三角剖分的理解又深刻了好多。

代码：

/* ***********************************************
Author :_rabbit
Created Time :2014/5/4 15:03:55
File Name :20.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-10
#define pi acos(-1.0)
typedef long long ll;
int dcmp(double x){
    if(fabs(x)0?1:-1;
}
struct Point{
    double x,y;
    Point(double _x=0,double _y=0){
        x=_x;y=_y;
    }
};
Point operator + (const Point &a,const Point &b){
    return Point(a.x+b.x,a.y+b.y);
}
Point operator - (const Point &a,const Point &b){
    return Point(a.x-b.x,a.y-b.y);
}
Point operator * (const Point &a,const double &p){
    return Point(a.x*p,a.y*p);
}
Point operator / (const Point &a,const double &p){
    return Point(a.x/p,a.y/p);
}
bool operator <(const Point &a,const Point &b){
    return a.x=0;
}
Point GetLineIntersection(Point p,Point v,Point q,Point w){
    Point u=p-q;
    double t=Cross(w,u)/Cross(v,w);
    return p+v*t;
}
Point GetLineIntersection(Line a,Line b){
    return GetLineIntersection(a.p,a.v,b.p,b.v);
}
double PolyArea(vector p){
    int n=p.size();
    double ans=0;
    for(int i=1;i=0;  
}  
bool OnCircle(Point x,Circle c){  
    return dcmp(c.r-Length(c.c-x))==0;  
}  
int getSegCircleIntersection(Line L,Circle C,Point *sol){  
    Point nor=Normal(L.v);  
    Line p1=Line(C.c,nor);  
    Point ip=GetLineIntersection(p1,L);  
    double dis=Length(ip-C.c);  
    if(dcmp(dis-C.r)>0)return 0;  
    Point dxy=vecunit(L.v)*sqrt(C.r*C.r-dis*dis);  
    int ret=0;  
    sol[ret]=ip+dxy;  
    if(OnSegment(sol[ret],L.p,L.point(1)))ret++;  
    sol[ret]=ip-dxy;  
    if(OnSegment(sol[ret],L.p,L.point(1)))ret++;  
    return ret;  
}  
double SegCircleArea(Circle C,Point a,Point b){  
    double a1=angle(a-C.c);  
    double a2=angle(b-C.c);  
    double da=fabs(a1-a2);  
    if(da>pi)da=pi*2-da;  
    return dcmp(Cross(b-C.c,a-C.c))*da*C.r*C.r/2.0;  
}  
double PolyCircleArea(Circle C,Point *p,int n){  
    double ret=0;  
    Point sol[2];  
    p[n]=p[0];  
    for(int i=0;i>x1>>y1>>R>>x2>>y2>>x3>>y3)  
    {  
		if(flag==0)flag=1;else puts("");
        Circle C=Circle(Point(x1,y1),R);  
        if(x2>x3)swap(x2,x3);
		if(y2>y3)swap(y2,y3);
        p[0]=Point(x2,y2);  
        p[2]=Point(x3,y3);  
        p[1]=Point(x3,y2);  
        p[3]=Point(x2,y3);  
		double ans=PolyCircleArea(C,p,4);
        printf("%.10lf\n",fabs(ans));       
    }
     return 0;  
}

/*
Point p[1000];
int main(){
	int n;Circle C;
	while(cin>>n>>C.c.x>>C.c.y>>C.r){
		for(int i=0;i>p[i].x>>p[i].y;
		cout<



ZOJ 1675  矩形与圆的面积交,,
ZOJ 1675  矩形与圆的面积交

推荐阅读

io
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]

蜡笔小新 2023-12-14 15:08:18
import
求解hdu 1003 java题目的动态规划优化方法

本文讨论了如何优化解决hdu 1003 java题目的动态规划方法，通过分析加法规则和最大和的性质，提出了一种优化的思路。具体方法是，当从1加到n为负时，即sum(1,n)sum(n,s)，可以继续加法计算。同时，还考虑了两种特殊情况：都是负数的情况和有0的情况。最后，通过使用Scanner类来获取输入数据。 ... [详细]

蜡笔小新 2023-12-14 13:11:00
数组
动态规划算法的基本步骤及最长递增子序列问题详解

本文详细介绍了动态规划算法的基本步骤，包括划分阶段、选择状态、决策和状态转移方程，并以最长递增子序列问题为例进行了详细解析。动态规划算法的有效性依赖于问题本身所具有的最优子结构性质和子问题重叠性质。通过将子问题的解保存在一个表中，在以后尽可能多地利用这些子问题的解，从而提高算法的效率。 ... [详细]

蜡笔小新 2023-12-13 15:38:19
数组
指针的引用以及在什么情况下使用指针的引用

本文介绍了指针的概念以及在函数调用时使用指针作为参数的情况。指针存放的是变量的地址，通过指针可以修改指针所指的变量的值。然而，如果想要修改指针的指向，就需要使用指针的引用。文章还通过一个简单的示例代码解释了指针的引用的使用方法，并思考了在修改指针的指向后，取指针的输出结果。 ... [详细]

蜡笔小新 2023-12-13 12:54:29
python
lua语言闭包、模式匹配、日期、编译、模块的特性及应用

本文介绍了lua语言中闭包的特性及其在模式匹配、日期处理、编译和模块化等方面的应用。lua中的闭包是严格遵循词法定界的第一类值，函数可以作为变量自由传递，也可以作为参数传递给其他函数。这些特性使得lua语言具有极大的灵活性，为程序开发带来了便利。 ... [详细]

蜡笔小新 2023-12-14 18:18:21
import
Java实现大数乘法（分治算法）

本文介绍了使用Java实现大数乘法的分治算法，包括输入数据的处理、普通大数乘法的结果和Karatsuba大数乘法的结果。通过改变long类型可以适应不同范围的大数乘法计算。 ... [详细]

蜡笔小新 2023-12-14 15:43:50
io
九度OnlineJudge之1002：Grading问题的解决方法

本文介绍了九度OnlineJudge中的1002题目“Grading”的解决方法。该题目要求设计一个公平的评分过程，将每个考题分配给3个独立的专家，如果他们的评分不一致，则需要请一位裁判做出最终决定。文章详细描述了评分规则，并给出了解决该问题的程序。 ... [详细]

蜡笔小新 2023-12-14 13:00:09
io
C#之数据集：DataSet对象的使用及相关方法详解

本文介绍了C#中数据集DataSet对象的使用及相关方法详解，包括DataSet对象的概述、与数据关系对象的互联、Rows集合和Columns集合的组成，以及DataSet对象常用的方法之一——Merge方法的使用。通过本文的阅读，读者可以了解到DataSet对象在C#中的重要性和使用方法。 ... [详细]

蜡笔小新 2023-12-14 12:09:13
import
OC学习笔记之@property和@synthesize

本文介绍了OC学习笔记中的@property和@synthesize，包括属性的定义和合成的使用方法。通过示例代码详细讲解了@property和@synthesize的作用和用法。 ... [详细]

蜡笔小新 2023-12-14 12:05:06
io
Open judge C16H: Magical Balls 快速幂+逆元问题解析

本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法，并给出了问题的解析和解决方法。详细介绍了问题的背景和规则，并给出了相应的算法解析和实现步骤。通过本文的解析，读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]

蜡笔小新 2023-12-14 12:03:27
io
Linux进程控制块PCBtask_struct结构体结构及作用详解

本文详细介绍了Linux中进程控制块PCBtask_struct结构体的结构和作用，包括进程状态、进程号、待处理信号、进程地址空间、调度标志、锁深度、基本时间片、调度策略以及内存管理信息等方面的内容。阅读本文可以更加深入地了解Linux进程管理的原理和机制。 ... [详细]

蜡笔小新 2023-12-13 21:31:18
数组
java 线程死锁模拟

1，关于死锁的理解死锁，我们可以简单的理解为是两个线程同时使用同一资源，两个线程又得不到相应的资源而造成永无相互等待的情况。 2，模拟死锁背景介绍：我们创建一个朋友 ... [详细]

蜡笔小新 2023-12-13 19:12:25
io
《数据结构》学习笔记3——串匹配算法性能评估

本文主要讨论串匹配算法的性能评估，包括模式匹配、字符种类数量、算法复杂度等内容。通过借助C++中的头文件和库，可以实现对串的匹配操作。其中蛮力算法的复杂度为O(m*n)，通过随机取出长度为m的子串作为模式P，在文本T中进行匹配，统计平均复杂度。对于成功和失败的匹配分别进行测试，分析其平均复杂度。详情请参考相关学习资源。 ... [详细]

蜡笔小新 2023-12-13 16:16:05
io
高质量SQL书写的30条建议

本文提供了30条关于优化SQL的建议，包括避免使用select *，使用具体字段，以及使用limit 1等。这些建议是基于实际开发经验总结出来的，旨在帮助读者优化SQL查询。 ... [详细]

蜡笔小新 2023-12-13 13:24:33
io
asp.net微信公众平台开发目录汇总陆续更新的相关内容

本文内容为asp.net微信公众平台开发的目录汇总，包括数据库设计、多层架构框架搭建和入口实现、微信消息封装及反射赋值、关注事件、用户记录、回复文本消息、图文消息、服务搭建（接入）、自定义菜单等。同时提供了示例代码和相关的后台管理功能。内容涵盖了多个方面，适合综合运用。 ... [详细]

蜡笔小新 2023-12-14 22:40:22

停留的烟蒂_984

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章