uva1308 Viva Confetti

2019-11-06 08:56:13

字体：大中小

来源：转载

供稿：网友

Do you know confetti ? They are small discs of colored paper, and people throw them around during parties or festivals. Since people throw lots of confetti, they may end up stacked one on another, so there may be hidden ones underneath. A handful of various sized confetti have been dropped on a table. Given their positions and sizes, can you tell us how many of them you can see? The following gure rePResents the disc con gura- tion for the rst sample input, where the bottom disc is still visible. Input The input is composed of a number of con gurations of the following form. n x 1 y 1 r 1 x 2 y 2 r 2 … x n y n r n The rst line in a con guration is the number of discs in the con guration (a positive integer not more than 100), followed by one Ine descriptions of each disc: coordinates of its center and radius, expressed as real numbers in decimal notation, with up to 12 digits after the decimal point. The imprecision margin is 5 10

一个圆被看见的部分的边界一定是若干个圆弧【不一定是自己的】拼成的，只需要枚举圆弧，把中点沿着半径向里、向外移动足够小的δ $/delta$ 判断这个点最上面的圆。因为圆弧有O(n2) $O(n^2)$ 个【两两相交】，复杂度O(n2) $O(n^2)$ 。

#include<cstdio>#include<cstring>#include<cmath>#include<vector>#include<algorithm>using namespace std;const double eps=5e-13,pi=acos(-1);int cmp(double x){ if (x>eps) return 1; if (fabs(x)<eps) return 0; return -1;}struct Vector{ double x,y; void rd() { scanf("%lf%lf",&x,&y); } Vector Operator + (const Vector &v) const { return (Vector){x+v.x,y+v.y}; } Vector operator - (const Vector &v) const { return (Vector){x-v.x,y-v.y}; } Vector operator * (const double &k) const { return (Vector){x*k,y*k}; } Vector operator / (const double &k) const { return (Vector){x/k,y/k}; }};typedef Vector point;double dot(Vector v,Vector u){ return v.x*u.x+v.y*u.y;}double cross(Vector v,Vector u){ return v.x*u.y-v.y*u.x;}double len(Vector v){ return sqrt(dot(v,v));}double dis(point p1,point p2){ return len(p2-p1);}double angle(Vector v){ return atan2(v.y,v.x);}struct circle{ point o; double r; void rd() { o.rd(); scanf("%lf",&r); }}a[110];point get(circle c,double a,double delta){ return (point){c.o.x+(c.r+delta)*cos(a),c.o.y+(c.r+delta)*sin(a)};}bool in(point p,circle c){ return cmp(dis(p,c.o)-c.r)<=0;}vector<double> ang[110];void intersectangle(int i,int j){ double d=dis(a[i].o,a[j].o); if (cmp(d-fabs(a[i].r-a[j].r))<=0||cmp(d-a[i].r-a[j].r)>=0) return; double x=angle(a[j].o-a[i].o),y=acos((a[i].r*a[i].r+d*d-a[j].r*a[j].r)/2/a[i].r/d); ang[i].push_back(x+y); ang[i].push_back(x-y);}int n;bool vis[110];void mark(point p){ for (int i=n;i;i--) if (in(p,a[i])) { vis[i]=1; return; }}int solve(){ int flag; double x,y; for (int i=1;i<=n;i++) a[i].rd(); memset(vis,0,sizeof(vis)); for (int i=1;i<=n;i++) { ang[i].clear(); for (int j=1;j<=n;j++) if (j!=i) intersectangle(i,j); if (ang[i].empty()) { mark(get(a[i],0,eps)); mark(get(a[i],0,-eps)); continue; } sort(ang[i].begin(),ang[i].end()); for (int j=0;j<ang[i].size()-1;j++) { x=(ang[i][j]+ang[i][j+1])/2; mark(get(a[i],x,eps)); mark(get(a[i],x,-eps)); } x=(ang[i][ang[i].size()-1]+ang[i][0]+2*pi)/2; mark(get(a[i],x,eps)); mark(get(a[i],x,-eps)); } int ans=0; for (int i=1;i<=n;i++) if (vis[i]) ans++; return ans;}int main(){ while (scanf("%d",&n)&&n) printf("%d/n",solve());}

上一篇：纯DOS下安装Linux

下一篇：Linux Ubuntu chrome flash player out of date chrome不能播放flash