程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> poj 2932 Coneology 掃面線法

poj 2932 Coneology 掃面線法

編輯:關於C++

題意:

給n個無交點的圓,求這n個圓中不被其它圓包含的圓。

分析:

掃面線法,用二叉樹(set+lowerbound方法)維護最外圓的集合。

代碼:

 

#include 
#include 
#include 
#include 
using namespace std;
const int maxN=40012;
double r[maxN],x[maxN],y[maxN];
int n;
vector > events;
set > outers;
vector res;

bool inside(int i,int j)
{
	double dx=x[i]-x[j],dy=y[i]-y[j],dr=r[i]-r[j];
	return r[i]<=r[j]&&dx*dx+dy*dy<=dr*dr;	
}

int main()
{
	scanf("%d",&n);
	for(int i=0;i >::iterator it=outers.lower_bound(make_pair(y[ids],ids));
			if(it!=outers.end()&&inside(ids,it->second)) continue;
			if(it!=outers.begin()&&inside(ids,(--it)->second)) continue;
			res.push_back(ids);
			outers.insert(make_pair(y[ids],ids));
		}else
			outers.erase(make_pair(y[ids],ids));			
	}
	sort(res.begin(),res.end());
	printf("%d\n",res.size());
	for(int i=0;i

 

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