QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#35051 | #851. (Almost) Fair Cake-Cutting | Froggygua | AC ✓ | 3ms | 3892kb | C++17 | 6.6kb | 2022-06-12 22:05:43 | 2022-06-12 22:05:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const double eps=1e-9;
const double PI=acos(-1.0);
const double inf=1e9+233;
//Vector可以用Point来表示
struct Point{
double x,y;
Point(double _x=0,double _y=0):x(_x),y(_y){}
//相等
friend bool operator ==(const Point &a,const Point &b){
return fabs(a.x-b.x)<eps&&fabs(a.y-b.y)<eps;
}
//不相等
friend bool operator !=(const Point &a,const Point &b){
return !(a==b);
}
//相加
friend Point operator + (const Point &a,const Point &b){
return Point(a.x+b.x,a.y+b.y);
}
//相减
friend Point operator - (const Point &a,const Point &b){
return Point(a.x-b.x,a.y-b.y);
}
//点积
friend double operator * (const Point &a,const Point &b){
return a.x*b.x+a.y*b.y;
}
//叉积
friend double operator % (const Point &a,const Point &b){
return a.x*b.y-a.y*b.x;
}
//长度
inline double len(){
return sqrt(x*x+y*y);
}
//单位向量
Point unit(){
double l=len();
return Point(x/l,y/l);
}
//求单位法向量
inline Point normal(){
double l=len();
return Point(-y/l,x/l);
}
//点从下往上排序
inline bool operator < (Point b){
return fabs(y-b.y)<eps?x<b.x:y<b.y;
}
//平面直角坐标系上半部分优先
inline bool Quad(){
return y>eps||(fabs(y)<=eps&&x>=-eps);
}
};
inline Point operator * (double k,Point a){
return Point(a.x*k,a.y*k);
}
//两个向量的夹角
inline double Angle(Point a,Point b){
//return acos(a*b/a.len()/b.len());
double tmp=atan2(b.y,b.x)-atan2(a.y,a.x);
while(tmp>=PI+eps)tmp-=2*PI;
while(tmp<=-PI-eps)tmp+=2*PI;
return tmp;
}
//判断两个向量是否平行
inline bool Para(Point a,Point b){
return fabs(a%b)<=eps;
}
//判断向量a是否在向量b的左侧
inline bool Left(Point a,Point b){
return b%a>eps;
}
//逆时针旋转p后的向量
inline Point Rotate(Point a,double p){
return Point(a.x*cos(p)-a.y*sin(p),a.x*sin(p)+a.y*cos(p));
}
//绕LTL逆时针排序
//直线
struct Line{
Point p[2];
Line(Point a=Point(0,0),Point b=Point(0,0)){p[0]=a,p[1]=b;}
inline Point& operator [] (int i){
return p[i];
}
inline Point v(){
return p[1]-p[0];
}
};
//直线交点
inline Point Cross(Line a,Line b){
return a[0]+((b[0]-a[0])%(b[1]-a[0]))/((a[1]-a[0])%(b[1]-b[0]))*(a[1]-a[0]);
}
//多边形
typedef vector<Point> Poly;
//面积
double Area(Poly A){
if(A.empty())return 0.0;
double tot=0;
for(int i=0;i<(int)A.size()-1;++i){
tot+=A[i]%A[i+1];
}
tot+=A[(int)A.size()-1]%A[0];
return fabs(tot)/2.0;
}
//周长
double C(Poly A){
double tot=0;
for(int i=0;i<(int)A.size()-1;++i){
tot+=(A[i+1]-A[i]).len();
}
tot+=(A[A.size()-1]-A[0]).len();
return tot;
}
//重心
Point Cent(Poly A){
double x=0,y=0,m=0;
for(int i=1;i<(int)A.size()-1;++i){
double tmp=(A[i]-A[0])%(A[i+1]-A[0]);
x+=tmp*(A[0].x+A[i].x+A[i+1].x)/3.0;
y+=tmp*(A[0].y+A[i].y+A[i+1].y)/3.0;
m+=tmp;
}
return Point(x/m,y/m);
}
//求凸包
Poly Convex(Poly A){
Point LTL=(*min_element(A.begin(),A.end())); //Lower Then Left
sort(A.begin(),A.end(),[&](Point a,Point b){
a=a-LTL,b=b-LTL;
return Para(a,b)?a.len()<b.len():Left(b,a);
});
Poly st;
for(auto p:A){
while(st.size()>1&&!Left(p-st[(int)st.size()-2],st.back()-st[(int)st.size()-2]))st.pop_back();
st.push_back(p);
}
return st;
}
// 求点是否在多边形内(单次询问,可以是凹多边形)
inline bool Inside_1(Poly A,Point p){
double tot=0;
for(int i=0;i<(int)A.size();++i)tot+=Angle(A[i]-p,A[(i+1)%A.size()]-p);
return fabs(tot)>=eps;
}
//多组询问
inline bool Inside_2(Poly &A,Point p){
if(p==A[0])return true;
if(Left(p-A[0],A[A.size()-1]-A[0])||Left(A[1]-A[0],p-A[0]))return false;
int pos=lower_bound(A.begin(),A.end()-1,p,[&](Point a,Point b){
a=a-A[0],b=b-A[0];
return Para(a,b)?a.len()<b.len():Left(b,a);
})-A.begin();
return !Left(A[pos]-A[pos-1],p-A[pos-1])&&A[0]<p;
}
//半平面交(HalfPlaneIntersection) <向量左侧>
inline bool cmpang(Point a,Point b){
return a.Quad()^b.Quad()?a.Quad()<b.Quad():Left(b,a);
}
inline bool operator <(Line a,Line b){
return Para(a.v(),b.v())&&(a.v()*b.v()>eps)?Left(a[0]-b[0],b.v()):cmpang(a.v(),b.v());
}
Poly HPI(vector<Line> L){
L.emplace_back(Point(-inf,-inf),Point(inf,-inf));
L.emplace_back(Point(inf,-inf),Point(inf,inf));
L.emplace_back(Point(inf,inf),Point(-inf,inf));
L.emplace_back(Point(-inf,inf),Point(-inf,-inf));
vector<Line> q(L.size()+10);
static int l,r;
sort(L.begin(),L.end());
Poly R;
r=1,q[l=1]=L[0];
for(int i=1;i<(int)L.size();++i){
if(Para(q[r].v(),L[i].v()))continue;
while(l<r&&Left(L[i].v(),Cross(q[r],q[r-1])-L[i][0]))--r;
while(l<r&&Left(L[i].v(),Cross(q[l],q[l+1])-L[i][0]))++l;
q[++r]=L[i];
if(l<r&&Para(q[r].v(),q[r-1].v())){
return R;
}
}
while(l<r&&Left(q[l].v(),Cross(q[r],q[r-1])-q[l][0]))--r;
while(l<r&&Left(q[r].v(),Cross(q[l],q[l+1])-q[r][0]))++l;
if(l==r)return R;
q[r+1]=q[l];
for(int i=l;i<=r;++i){
R.push_back(Cross(q[i],q[i+1]));
}
R.erase(unique(R.begin(),R.end()),R.end());
if(R.size()>1&&R[0]==R.back())R.pop_back();
return R;
}
//Minkowski
inline Poly operator + (const Poly &A,const Point &p){
Poly C=A;
for(auto &t:C)t=t+p;
return C;
}
inline Poly operator + (const Poly &A,const Poly &B){
if(A.empty())return B;
if(B.empty())return A;
if(A.size()==1)return B+A[0];
if(B.size()==1)return A+B[0];
Poly R;
int i=0,j=0;
R.push_back(A[0]+B[0]);
while(true){
Point vA=A[(i+1)%A.size()]-A[i],vB=B[(j+1)%B.size()]-B[j];
if(Para(vA,vB)?vA.Quad()==vB.Quad():Left(vA,vB)){
i=(i+1)%A.size();
}
else{
j=(j+1)%B.size();
}
R.push_back(A[i]+B[j]);
if(!i&&!j)break;
}
R.pop_back();
return R;
}
int n,m;
void Solve(){
cin>>n>>m;
vector<Line> A(n);
for(int i=0;i<n;++i){
int a,b,c;
cin>>a>>b>>c;
if(!b){
A[i][0]=Point(-1.0*c/a,0);
A[i][1]=Point(-1.0*c/a,1);
}
else{
A[i][0]=Point(0,-1.0*c/b);
A[i][1]=Point(1,(-1.0*c-a)/b);
}
}
if(n>=3){
cout<<100.0<<"%"<<'\n';
return;
}
double ans=m*m;
for(int s=0;s<(1<<n);++s){
vector<Line> L;
L.emplace_back(Point(0,0),Point(m,0));
L.emplace_back(Point(m,0),Point(m,m));
L.emplace_back(Point(m,m),Point(0,m));
L.emplace_back(Point(0,m),Point(0,0));
for(int i=0;i<n;++i){
if(!(s>>i&1)){
L.emplace_back(A[i][0],A[i][1]);
}
else{
L.emplace_back(A[i][1],A[i][0]);
}
}
ans=min(ans,Area(HPI(L)));
}
cout<<100.0*(1.0-ans/(m*m))<<"%"<<'\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.setf(ios::fixed);
cout.precision(10);
int T;
cin>>T;
while(T--){
Solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3744kb
input:
1 2 1000 0 1 -750 1 0 -750
output:
93.7500000000%
result:
ok OK!
Test #2:
score: 0
Accepted
time: 3ms
memory: 3848kb
input:
500 1 1000 1 0 -300 1 1000 1 1 -500 1 1000 1 1 -1000 1 2 0 -1 1 1 1 -1 -1 1 1 1000 -866 287 1 1 1 3 -442 1 1 130 -628 558 0 1 868 -297 166 1 1 479 373 3 -96709 1 68 527 -833 0 1 348 -337 954 -109611 1 917 564 2 -449502 1 16 679 -175 0 1 463 138 -961 3 1 361 -951 -12 45113 1 464 -977 622 -35388 1 351...
output:
70.0000000000% 87.5000000000% 50.0000000000% 50.0000000000% 50.0000000000% 83.4294457275% 99.4343891403% 55.5732484076% 72.0534841503% 53.7259258845% 68.3673469388% 50.6786308104% 86.7353844250% 87.1134020619% 92.8193049447% 87.4903513141% 75.4955418490% 99.9392694441% 79.4988172856% 99.7911555184% ...
result:
ok OK!
Test #3:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
50 4000 1000 -866 287 1 -246 141 188157 994 0 -948594 3 -442 1 172 -257 2 -77 -628 557282 -983 -297 165987 -172 -992 4695 961 587 -844056 -981 631 897222 289 1 -184824 -463 493 -336717 954 -110 32323 67 866 -240824 893 -111 -546885 259 -818 385562 906 93 -191311 308 -794 258487 502 -855 -273835 -649...
output:
100.0000000000% 100.0000000000% 100.0000000000% 100.0000000000% 100.0000000000% 100.0000000000% 100.0000000000% 100.0000000000% 100.0000000000% 100.0000000000% 100.0000000000% 100.0000000000% 100.0000000000% 100.0000000000% 100.0000000000% 100.0000000000% 100.0000000000% 100.0000000000% 100.00000000...
result:
ok OK!