ECNA 2018 D pizzacutting

题目大意：有些脑子缺根筋的人非要把蛋糕沿着水平和竖直的方向切，这会导致切出来的有些块很小没有卵用。定义面积与最大的比值小于p的为没有卵用的块，问切出来有多少个这样的块。输入r, dx, dy, x, y, p，代表半径、每次切的间隔、其中一个交点坐标。输入均为整数，r<=3000, dx,dy,x,y<=10000。

这个数据范围r<=3000，时限又长，所以暴力枚举矩形套圆和多边形交计算集合板子没问题。注意稍微优化一下，枚举矩形的起点和终点不超过圆的半径，否则会t。四个点在圆里面也没必要再算了。

```
#include <bits/stdc++.h>
```
```
using namespace std;
```
```
 
```
```
typedef double db;
```
```
const db PI=acos(-1),eps=1e-8;
```
```
 
```
```
bool eq(db x){return fabs(x)<eps;}
```

int sgn(db x){if (x<-eps) return -1; return x>eps;}

```
 
```
```
#define Vec const vec &
```
```
#define Point const point &
```
```
struct vec{
```
```
	db x,y;
```
```
	vec():x(0),y(0){}
```
```
	vec(db x, db y):x(x),y(y){}
```

	vec operator+(Vec v) const{return vec(x+v.x,y+v.y);}

	vec operator-(Vec v) const{return vec(x-v.x,y-v.y);}

	vec operator*(db a) const{return vec(x*a,y*a);}

	vec operator/(db a) const{return vec(x/a,y/a);}

```
 
```

	db operator|(Vec v) const{return x*v.x+y*v.y;}

	db operator&(Vec v) const{return x*v.y-y*v.x;}

	db operator!() const{return sqrt(x*x+y*y);}

```
};
```
```
typedef vec point;
```

db angle(Vec a, Vec b){return fabs(atan2(a&b,a|b));}

db cross(Vec a, Vec b, Vec c){return b-a&c-a;}

```
struct circle{
```
```
	point c; db r;
```
```
};
```

int segInt(Vec a, Vec b, circle c, point *ans){

```
	vec v=b-a, u=a-c.c;
```
```
	db e=v|v, f=v|u*2, g=(u|u)-c.r*c.r;
```
```
	db delta=f*f-4*e*g;
```
```
	if(delta<0) return 0;
```
```
	if (eq(delta)){
```
```
		db t=f/2/e;
```

		if (sgn(t)>=0 && sgn(t-1)<=0) return ans[0]=a-v*t,1;

```
		return 0;
```
```
	}
```
```
	db t1=(-f-sqrt(delta))/(2*e);
```
```
	db t2=(-f+sqrt(delta))/(2*e);
```
```
	point a1=a+v*t1, a2=a+v*t2;
```
```
	int cnt=0;
```

	if (sgn(t1)>=0 && sgn(t1-1)<=0) ans[cnt++]=a1;

	if (sgn(t2)>=0 && sgn(t2-1)<=0) ans[cnt++]=a2;

```
	return cnt;
```
```
}
```
```
 
```

db secarea(Vec a, Vec b, db r){return r*r*angle(a,b)/2;}

db triarea(Vec a, Vec b){return fabs(a&b)/2;}

```
 
```

db tri_cirarea(vec p1,vec p2, circle c){

```
	db r=c.r;
```
```
	p1=p1-c.c; p2=p2-c.c;
```
```
	c.c=vec(0,0);
```
```
	point p[2];
```
```
	if (sgn(!p1-r)<0){
```

		if (sgn(!p2-r)<0) return triarea(p1, p2);

```
		segInt(p1,p2,c,p);
```

		return triarea(p1,p[0])+secarea(p[0],p2,r);

```
	}
```
```
	if (sgn(!p2-r)<0){
```
```
		segInt(p1,p2,c,p);
```

		return secarea(p1,p[0],r)+triarea(p[0],p2);

```
	}
```
```
	int pc=segInt(p1,p2,c,p);
```

	if (pc==2) return secarea(p1,p[0],r)+triarea(p[0],p[1])+secarea(p[1],p2,r);

```
	return secarea(p1,p2,r);
```
```
}
```
```
 
```

db poly_cirarea(point *p, int n, circle c){

```
	db ans=0;
```
```
	for (int i=0;i<n;i++){
```
```
		db d=sgn(cross(c.c,p[i],p[(i+1)%n]));
```

		ans+=d*tri_cirarea(p[i],p[(i+1)%n],c);

```
	}
```
```
	return fabs(ans);
```
```
}
```
```
 
```
```
db ar[10000000]; int arc;
```
```
 
```
```
int main(){
```
```
	db x,y,dx,dy,r,p;
```
```
	while (cin>>r>>dx>>dy>>x>>y>>p){
```
```
		int ans=0;db maxa=0;
```
```
		for(;x<0;x+=dx);
```
```
		for(;y<0;y+=dy);
```
```
		for(;x>-r;x-=dx);
```
```
		for(;y>-r;y-=dy);
```
```
		for (db i=x;i<r;i+=dx)
```
```
			for (db j=y;j<r;j+=dy){
```

				point p[4]={vec(i,j),vec(i+dx,j),vec(i+dx,j+dy),vec(i,j+dy)};

```
				db a;
```

				if (!p[0]<r && !p[1]<r && !p[2]<r && !p[3]<r) a=dx*dy;

				else a=poly_cirarea(p,4,(circle){vec(0,0),r});

				if (a>eps) ar[arc++]=a; maxa=max(a,maxa);

```
			}
```

		for (int i=0;i<arc;i++) {if(ar[i]/maxa<p+1e-6) ans++;}

```
		cout<<ans<<'\n';
```
```
	}
```
```
	return 0;
```
```
}
```

fffasttime

ECNA 2018 D pizzacutting

发表评论取消回复

发表评论 取消回复

发表评论取消回复