程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BZOJ 1043 HAOI2008 下落的圓盤 計算幾何

BZOJ 1043 HAOI2008 下落的圓盤 計算幾何

編輯:C++入門知識

BZOJ 1043 HAOI2008 下落的圓盤 計算幾何


題目大意:n個圓盤依次下落,求最終能看到的輪廓線面積

円盤反對!讓我們一起團結起來!趕走円盤!

咳咳。很神的一道題 今天去看了題解和白書才搞出來……

首先我們倒著做 對於每個圓盤處理出在它之後落下的圓盤和它的覆蓋區間 然後求一個區間並就能算出這個圓盤的可見弧長

然後就是相交部分怎麼求的問題了

首先兩個圓必須相交 然後作圓心1到圓心2的向量 用atan2求出極角 然後利用余弦定理求出兩個交點和圓心連線的夾角即可 注意區間不在[0,2π]的部分要分割成另一個區間

處理起來其實不是很麻煩……都是技♂巧的問題

#include
#include
#include
#include
#include
#define M 1010
#define PI 3.1415926536
using namespace std;
struct point{
	double x,y;
};
struct circle{
	point o;
	double r;
}a[M];
int n;
double ans;
pairintervals[M<<1];int tot;
inline double Distance(const point &p1,const point &p2)
{
	return sqrt( (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y) );
}
void Calculate(const circle o1,const circle o2,const double &dis)
{
	double alpha=atan2(o2.o.y-o1.o.y,o2.o.x-o1.o.x)+PI;
	double delta=acos((o1.r*o1.r+dis*dis-o2.r*o2.r)/(2*o1.r*dis));
	pairtemp(alpha-delta,alpha+delta);
	if(temp.first>=0&&temp.second<=2*PI)
		intervals[++tot]=temp;
	else if(temp.first<0)
		intervals[++tot]=make_pair(temp.first+2*PI,2*PI),intervals[++tot]=make_pair(0,temp.second);
	else
		intervals[++tot]=make_pair(temp.first,2*PI),intervals[++tot]=make_pair(0,temp.second-2*PI);
}
double Interval_Union()
{
	int i;
	double re=0,st=-1,ed=-1;
	sort(intervals+1,intervals+tot+1);
	for(i=1;i<=tot;i++)
	{
		if(intervals[i].first>ed)
			re+=ed-st,st=intervals[i].first,ed=intervals[i].second;
		else
			ed=max(ed,intervals[i].second);
	}
	re+=ed-st;
	return 2*PI-re;
}
int main()
{
	int i,j;
	cin>>n;
	for(i=n;i;i--)
		scanf("%lf%lf%lf",&a[i].r,&a[i].o.x,&a[i].o.y);
	for(i=1;i<=n;i++)
	{
		tot=0;
		for(j=1;jdis)
				break;
			if(a[i].r+a[j].r>dis&&fabs(a[i].r-a[j].r)

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved