问题 J: 豆豆强的蛋糕店
问题 J: 豆豆强的蛋糕店
内存限制：128 MB时间限制：1 S标准输入输出
题目描述
豆豆强是一个人名，曾经是一名ACMer。
通过打斗地主、录视频、作解说、开淘宝店等，豆豆强终于成功走上了致富之路。
资金充足的豆豆强最近开了一家蛋糕店，作为一名特立独行的人，豆豆强受不了普通顾客要多少就卖给顾客多少蛋糕的运营模式，于是他提出了一种随机卖蛋糕模式，对于来买蛋糕的顾客，豆豆强会根据顾客购买蛋糕的多少提供不同长度的木棍，然后顾客随机投掷到蛋糕表面上（保证木棍不会插在蛋糕上，但有可能没有投掷到蛋糕上），那么这根木棍绕蛋糕中心（也是坐标原点）旋转一周后覆盖的蛋糕就是顾客获得的蛋糕。
注：由于工艺问题，豆豆强的蛋糕店只生产表面是长方形的蛋糕。
输入格式
输入数据第一行是case数T(1<= T <= 1000)；
接下来有T组case，每组case第一行三个整数n,m,sum，分别表示蛋糕的长、宽和顾客要买的蛋糕面积；
第二行四个整数x1,y1,x2,y2,表示顾客投掷木棍的两端点坐标。
1<= m <= n <= 1000
-1000<= x1,y1,x2,y2 <=1000
输出格式
如果顾客获得的蛋糕面积大于等于顾客想要的输出”YES”，否则输出”NO”。
每组数据输出一行。
输入样例 复制
2
4 4 4
0 2 3 4
10 10 65
0 2 3 4
输出样例 复制
NO
YES
代码：
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define PI 3.1415926535898
using namespace std;
double PointToPoint(double x1,double y1,double x2,double y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double PointToSegDist(double x,double y,double x1,double y1,double x2,double y2)
{
double cross=(x2-x1)*(x-x1)+(y2-y1)*(y-y1);
if(cross<=0)
return sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));
double ab2=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
if(cross>=ab2)
return sqrt((x-x2)*(x-x2)+(y-y2)*(y-y2));
double r=cross/ab2;
double dx=x1+(x2-x1)*r;
double dy=y1+(y2-y1)*r;
return sqrt((x-dx)*(x-dx)+(y-dy)*(y-dy));
}
double AraeToArcuate(double m,double r)
{
return acos(m/r)*r*r-sqrt(r*r-m*m)*m;
}
double CircularAreaRectangle(double n,double m,double r)
{
if(n>m)
{
double t=n;n=m;m=t;
}
double diagonal=sqrt(n*n+m*m);
if(r<n)
return PI*r*r;
else if(n<=r && r<=m)
return PI*r*r-2*(acos(n/r)*r*r-sqrt(r*r-n*n)*n);
else if(m<r && r<=diagonal)
return PI*r*r-2*(acos(n/r)*r*r-sqrt(r*r-n*n)*n)-2*(acos(m/r)*r*r-sqrt(r*r-m*m)*m);
else
return m*n*4;
}
int main()
{
int T;
cin >> T;
while(T--)
{
double n,m,sum;
double x1,x2,y1,y2;
cin >> n >> m >> sum;
cin >> x1 >> y1 >> x2 >> y2;
double x=0,y=0;
double near=PointToSegDist(x,y,x1,y1,x2,y2);
double d1=PointToPoint(x,y,x1,y1);
double d2=PointToPoint(x,y,x2,y2);
double far=d1>d2?d1:d2;
double area1=CircularAreaRectangle(n/2,m/2,near);
double area2=CircularAreaRectangle(n/2,m/2,far);
double area=area2-area1;
cout << (area>=sum||sum==0?"YES\n":"NO\n");
}
return 0;
}评论