QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#265908#7734. Intersection over Unionucup-team052WA 1443ms3756kbC++232.9kb2023-11-25 22:20:112023-11-25 22:20:11

Judging History

你现在查看的是最新测评结果

  • [2023-11-25 22:20:11]
  • 评测
  • 测评结果:WA
  • 用时:1443ms
  • 内存:3756kb
  • [2023-11-25 22:20:11]
  • 提交

answer

#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ "="),debug_helper::debug(__VA_ARGS__),D("\n")
#include"/home/xay5421/debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define each(x,v) for(auto&x:v)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
template<class T>void rd(T&x){int f=0,c;while(!isdigit(c=getchar()))f^=!(c^45);x=(c&15);while(isdigit(c=getchar()))x=x*10+(c&15);if(f)x=-x;}
template<class T>void pt(T x,int c=-1){if(x<0)putchar('-'),x=-x;if(x>9)pt(x/10);putchar(x%10+48);if(c!=-1)putchar(c);}
using namespace std;
using LL=long long;
using ULL=unsigned long long;
// mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
mt19937 rng(0);
int T;
struct vec{
	double x,y;
	bool operator<(const vec&rhs)const{
		return y<rhs.y;
	}
	vec operator-(const vec&rhs)const{return (vec){x-rhs.x,y-rhs.y};}
}a[4];
double cross(const vec&lhs,const vec&rhs){return lhs.x*rhs.y-lhs.y*rhs.x;}
double sqr(double x){return x*x;}
int main(){
#ifdef xay5421
	freopen("a.in","r",stdin);
#endif
	rd(T);
	while(T--){
		rep(i,0,3){
			scanf("%lf%lf",&a[i].x,&a[i].y);
		}
		if(a[0].x==a[1].x||a[0].y==a[1].y){
			puts("1");
			continue;
		}
		rotate(a,min_element(a,a+4),a+4);
		if(a[1].x>a[0].x){
			reverse(a+1,a+4);
		}
		double S0=cross(a[3]-a[0],a[1]-a[0]);
		auto F=[&](double X,double Y,double x,double y)->double{
			double k=(X/Y*(Y-y)-x)/X;
			return X*Y*k*k;
		};
		auto G=[&](double X,double Y,double x,double y)->double{
			double k=sqrt(sqr(y)+sqr(y/Y*X))/X;
			return X*Y*k*k;
		};
		auto IoU=[&](double x,double y){
			double s1=F(a[0].x-a[1].x,a[1].y-a[0].y,x-a[1].x,y-a[0].y);
			double s2=F(a[3].x-a[0].x,a[3].y-a[0].y,a[3].x-(a[1].x+a[3].x-x),y-a[0].y);
			double s3=G(a[0].x-a[1].x,a[1].y-a[0].y,x-a[1].x,y-a[0].y);
			double s4=G(a[3].y-a[0].y,a[3].x-a[0].x,y-a[0].y,a[3].x-(a[1].x+a[3].x-x));
			return (S0-s3-s4)/(S0+s1+s2);
		};
		double lx=a[1].x;
		double rx=a[0].x;
		double ly=a[0].y;
		double ry=a[1].y;
		uniform_real_distribution<double> xs(lx,rx);
		uniform_real_distribution<double> ys(ly,ry);
		auto valid=[&](double x,double y){
			return cross(a[0]-(vec){x,y},a[1]-(vec){x,y})>=0;
		};
		auto W=[&](double x){
			double L=ly,R=ry;
			while(R-L>=(L>0?max(1.,L):R<0?max(1.,-R):1)*1e-11){
				double mid1=L*2/3+R/3;
				double mid2=L/3+R*2/3;
				if(!valid(x,mid2)){
					R=mid2;
					continue;
				}
				if(IoU(x,mid1)>IoU(x,mid2)){
					R=mid2;
				}else{
					L=mid1;
				}
			}
			return IoU(x,L);
			
		};
		double L=lx,R=rx;
		while(R-L>=(L>0?max(1.,L):R<0?max(1.,-R):1)*1e-11){
			double mid1=L*2/3+R/3;
			double mid2=L/3+R*2/3;
			if(W(mid1)>W(mid2)){
				R=mid2;
			}else{
				L=mid1;
			}
		}
		printf("%.20f\n",W(L));
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3756kb

input:

3
0 2 2 0 0 -2 -2 0
7 -2 9 -2 9 2 7 2
7 13 11 10 5 2 1 5

output:

0.70710678118654735069
1
0.62384322483109366786

result:

ok 3 numbers

Test #2:

score: -100
Wrong Answer
time: 1443ms
memory: 3560kb

input:

10000
-568767734 379152673 -565681345 -54946093 -131582579 -51859704 -134668968 382239062
-194884120 -559906233 -194884142 -158042604 -998611400 -158042648 -998611378 -559906277
459335966 -945199065 478030260 -934243779 450535683 -887326546 431841389 -898281832
-483567491 491964356 -523827401 408140...

output:

0.99296541252646997044
0.99999993156882693857
0.59086981567862595366
0.62177048491080377790
0.57883238413512727583
1
0.49999999737417555323
0.68523458056392450022
0.45361597933154990114
0.50028739390208487592
0.98029611059210497448
0.49196753831289846692
0.54403738870671081163
0.36331124805507758468...

result:

wrong answer 9th numbers differ - expected: '0.4559617', found: '0.4536160', error = '0.0023457'