test 190802 生日蛋糕
|
生日蛋糕(Birthday) 输入文件:cake.in 输出文件:cake.out 时间限制:1s 空间限制:32M 问题描述 今天是你的妹妹的生日。依照传统,她将亲手将自己的圆形生日蛋糕切开。但她还太小擅长切蛋糕。她的每一刀都彻底穿过整个蛋糕。当然 她一定要不停的切好不容易蛋糕切完了你想知道它到底被切成了多少块。直接手 算是不现实的并写了一个程序来帮你数。 你的任务是:给定妹妹的切法你可以认为每一刀 的痕迹没有厚度输入 第一行包含一个数 r,表示圆形蛋糕的直径(1≤r≤1000)。蛋糕被放在一个 x-y 坐标系上心在(0,0)。 第二行包含一个数 n,表示妹妹切的刀数(1≤n≤1000)。 接下来 n 行每行描述一刀x1,y1,x2,y2 表示此刀的轨迹是从(x1,y1) 到(x2,y2),这两个点都在蛋糕的外面:可能有多刀的 轨迹交于同一点。 输出 输出一个整数样例输入 10 3 -15 15 15 -15 1 12 -6 -12 10 4 -10 -8 样例输出 7 说明 输入样例蛋糕半径为 10。第一刀从(-15,15)切到(15,-15),第二刀从(1,12)到(-6, -12),第三刀从(10,4)到(-10,-8)。所以整个蛋糕被分成了 7 份7。 评分 对于每一个测试点你将得到 100%的分数对于近 20%的数据? ? ? 这一题要通过自己画图找规律 可以发现新加入一条直线，假设它与之前的直线在圆内产生了$p$个不同的交点 那么它对答案的贡献就是$p+1$ 然后考虑怎么求交点 一条直线的方程可以写成$A*x+B*y+C=0$ 对于给定的两点$(x_1,y_1),(x_2,y_2)$，他们的方程中$A=y_2-y_1,B=x_2-x_1,C=x_1*y_2-y_1*x_2$ 对于$l_1=A_1*x+B_1*y+C_1,l_2=A_2*x+B_2*y+C_2$，它们的交点$(X,Y)$满足$A_1*X+B_1*Y+C_1=A_2*X+B_2*Y+C_2$ 二元一次方程组解出$(X,Y)$ 最后还要注意精度问题，$eps$取$10^{-7}$到$10^{-8}$就可以过了 听老师说两直线求交点的正解貌似要用到叉积，这样可以避免因为精度产生的错误 看了一下，感觉很难写的样子 然而叉积联赛不考(其实是我懒)就暂时放一边啦 ? #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1005; const double eps=1e-7; int n,r,ans; struct line{double a,b,c;} L[N]; struct node{double x,y;} Nd[N*N],tmp[N*N]; int cnt; bool cmp(node u,node v) {return u.x<v.x;} void solve(int l1,int l2) { double tx=(L[l1].c*L[l2].b-L[l2].c*L[l1].b)/(L[l1].b*L[l2].a-L[l1].a*L[l2].b); double ty=(L[l1].c*L[l2].a-L[l1].a*L[l2].c)/(L[l2].b*L[l1].a-L[l1].b*L[l2].a); if(tx<=1000.0 && ty<=1000.0) { //cout<<tx<<" "<<ty<<endl; if(tx*tx+ty*ty<=(double)(r*r)) Nd[++cnt].x=tx,Nd[cnt].y=ty; } } int main() { freopen("cake.in","r",stdin); freopen("cake.out","w",stdout); scanf("%d%d",&r,&n); for(int i=1;i<=n;++i) { int a,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); L[i].a=b-d,L[i].b=c-a,L[i].c=1ll*a*d-1ll*b*c; } ans=1; for(int i=1;i<=n;++i) { cnt=0; int p=0; for(int j=1;j<i;++j) solve(i,j); sort(Nd+1,Nd+cnt+1,cmp); tmp[0].x=tmp[0].y=-1000.0; for(int i=1;i<=cnt;++i) if(abs(tmp[p].x-Nd[i].x)>eps || abs(tmp[p].y-Nd[i].y)>eps) tmp[++p]=Nd[i]; //cout<<p<<endl; ans+=p+1; } printf("%d",ans); return 0; } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |