欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【UVALive 2572】计算几何-离散化

程序员文章站 2022-04-02 17:46:06
...

题意:按顺序给若干个圆,问最后多少个圆盘可见

题解:按照大白上的思路,针对每个圆,求它被其他圆分割成了多少段圆弧,包括不被分割,自己就是一个圆弧的情况。

求出所有圆弧之后,然后判断每段小圆弧内外两侧的可见圆盘。具体来说,把小圆弧重点P往内外各移动一个很小的距离,得到P1,P2,然后标记包含这两个点的圆盘中最顶部那个为可见的。【这段没看懂,为什么一定要移动?】

AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define maxn 106
using namespace std;
int n;
int vis[maxn];
vector<double>sol;
struct Point{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y){}
}p[maxn];
const double PI=acos(-1);
typedef Point Vector;

Vector operator + (Vector A,Vector B){
    return Vector(A.x+B.x,A.y+B.y);
}
Vector operator - (Vector A,Vector B){
    return Vector(A.x-B.x,A.y-B.y);
}
Vector operator * (Vector A,double p){
    return Vector(A.x*p,A.y*p);
}
Vector operator / (Vector A,double p){
    return Vector(A.x/p,A.y/p);
}

bool operator < (const Point& a,const Point& b){
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}

const double eps=1e-13;
int dcmp(double x){
    if(fabs(x)<eps) return 0;
    else return x<0?-1:1;
}

bool operator == (const Point& a,const Point&b){
    return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0;
}

//求向量叉积
double Cross(Vector A,Vector B){
    return A.x*B.y-A.y*B.x;
}

//点积
double Dot(Vector A,Vector B){
    return A.x*B.x+A.y*B.y;
}
//向量长度
double Length(Vector A){
    return sqrt(Dot(A,A));
}
double NormalizeAngle(double a){   //把(-180,180] 转化为 [0,360)
	return fmod(a+2*PI,2*PI);
}
//向量间夹角
double Angle(Vector A,Vector B){
    return acos(Dot(A,B)/Length(A)/Length(B));
}
//求与x轴的夹角
double Angle(Point v) {return atan2(v.y,v.x);}
void getCircleCircleIntersection(Point C1, double r1, Point C2, double r2,vector<double>& sol){
	double d = Length(C1-C2);
	if(dcmp(d)==0) return;
	if(dcmp(r1+r2-d)<0) return;
	if(dcmp(fabs(r1-r2)-d>0)) return; //内含,相离
 
	double ang=Angle(C2-C1);
	double dang=acos((r1*r1+d*d-r2*r2)/2/r1/d);
	sol.push_back(NormalizeAngle(ang+dang));
	if(dcmp(dang)!=0) sol.push_back(NormalizeAngle(ang-dang));
}
struct Circle{
    Point c;
    double r;
    Circle(Point c=Point(0,0),double r=0):c(c),r(r){}
}c[maxn];
inline Point point(Point p,double ang,double r){
	return Point(p.x+r*cos(ang),p.y+r*sin(ang));
}
void UpdateTop(Point p){
	for(int i=n-1;i>=0;i--){//遍历所有圆 ,逆序 
		double dist=Length(p-c[i].c);//计算该点与每一个圆圆心的距离 
		if(dcmp(dist-c[i].r)<0) { //如果 这个距离比该圆半径小 ,说明该弧在这个圆下面 ,最后遮挡该段弧的必为可见的。 
			vis[i]=1; break; 
		}
	}
}

int main(){
	int cas=1;
	
	while(~scanf("%d",&n)&&n){
		for(int i=0;i<n;i++){
			scanf("%lf%lf%lf",&c[i].c.x,&c[i].c.y,&c[i].r);
		}
		memset(vis,0,sizeof(vis));
		for(int i=0;i<n;i++){
			sol.clear();
			sol.push_back(0);//被包含 ,起始点 
			sol.push_back(2*PI);//没被任何圆切割 
			
			for(int j=0;j<n;j++){
				if(i==j) continue;
				getCircleCircleIntersection(c[i].c,c[i].r,c[j].c,c[j].r,sol);
			}
		/*	if(sol.size()==2) {
				vis[i]=1;
				continue;
			}*/
			sort(sol.begin(),sol.end());
			vector<double>::iterator it=unique(sol.begin(), sol.end());//返回整理之后的尾指针 
			sol.erase(it,sol.end());//删掉重复点  			
 			
			for(int k=0;k<sol.size()-1;k++){//针对这个圆被切割之后的每个弧的中心点 
				for(int side=-1;side<=1;side+=2){
					double nr=c[i].r+side*eps*2;
					UpdateTop(point(c[i].c,(sol[k]+sol[k+1])/2,nr));//取圆弧中点,然后把两个偏移之后的半径都放进去 
				}
			} 
		}
		int cnt=0;
		for(int i=0;i<n;i++)
			if(vis[i]) cnt++;
		printf("%d\n", cnt);
	}
	
	return 0;
}

相关标签: ACM 计算几何