先贴一下大神的链接。写得非常简练啊 http://blog.csdn.net/commonc/article/details/51392221
考虑把一个圆当做左右括号，每次扫到圆的左端点就相当于找到一个左括号，入栈；扫到圆的右端点，就和左括号一起出栈。 其实这道题目有个非常重要的性质：圆两两之间无交点。这个性质在很多地方要用，首先就是上面的做法就要用到。 然后考虑怎么判断这个圆的面积是加的还是减的。一开始我自己yy了一个算法，大概就是看一下距离当前最近的那条弧是凸的还是凹的，凸的说明那个圆和自己的情况是相同的，凹的说明自己被那个圆包含。后来想了一下好麻烦。。。 上面链接中的做法意思差不多，但是想起来简单很多。具体可以看代码。对于已经处理过的圆，分成两半存在set里面，下半弧是-1，上半弧是1。然后从左端点射出一条竖直向上的线，找到第一个相交的点（就是upper_bound那部分），如果这个点是下半弧的一部分（凸的），那么那个圆和自己的情况是相同的，如果这个点是上半弧的一部分（凹的），说明自己被那个圆包含。如果相切的话显然优先当做下半弧考虑。
#include<set>#include<cmath>#include<cstdio>#include<vector>#include <queue>#include<cstring>#include<iomanip>#include<stdlib.h>#include<iostream>#include<algorithm>#define ll long long#define inf 1000000000#define mod 1000000007#define N 400005#define fo(i,a,b) for(i=a;i<=b;i++)#define fd(i,a,b) for(i=a;i>=b;i--)using namespace std;struct cir{ll x,y,r;}c[N];struct pnt{ll num,x,kind;}b[N];set<pnt> S;ll n,i,nw,k;int f[N];ll sqr(ll x) {return x*x;}bool cmp(const pnt &x,const pnt &y) {return x.x<y.x;}bool Operator <(pnt x,pnt y) { double xx=c[x.num].y+x.kind*sqrt(sqr(c[x.num].r)-sqr(nw-c[x.num].x)); double yy=c[y.num].y+y.kind*sqrt(sqr(c[y.num].r)-sqr(nw-c[y.num].x)); if(xx!=yy) return xx<yy; return x.kind<y.kind; } int main(){ scanf("%lld",&n); fo(i,1,n) { scanf("%lld%lld%lld",&c[i].x,&c[i].y,&c[i].r); b[++k] = (pnt){i,c[i].x-c[i].r,1}; b[++k] = (pnt){i,c[i].x+c[i].r,-1}; } sort(b+1,b+k+1,cmp); set<pnt>::iterator it; fo(i,1,k) { nw = b[i].x; if (b[i].kind == 1) { it = S.upper_bound((pnt){b[i].num,0,-1}); //找当前左端点向上碰到的第一条弧 if (it == S.end()) f[b[i].num] = 1; else { if ((*it).kind == 1) f[b[i].num] = -f[(*it).num]; //如果是上半弧，说明被包含 else f[b[i].num] = f[(*it).num]; //如果是下半弧，说明包含情况和那个圆相同 } S.insert((pnt){b[i].num,0,-1});//插入两条弧 S.insert((pnt){b[i].num,0,1}); } else { S.erase((pnt){b[i].num,0,-1});//删去两条弧 S.erase((pnt){b[i].num,0,1}); } } ll res = 0; fo(i,1,n) res+=sqr(c[i].r)*f[i]; PRintf("%lld",res); }新闻热点
疑难解答
