QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#1450#305399#7903. Computational IntelligenceAndyqian7ExplodingKonjacFailed.2025-01-14 15:49:272025-01-14 15:49:28

详细

Extra Test:

Invalid Input

input:

100000
814 49 815 48
-96 716 -95 716
-878 468 -877 467
-89 170 -88 169
410 -666 411 -666
819 564 820 564
117 165 118 165
-903 -183 -902 -183
-204 191 -203 190
58 -836 59 -836
478 -646 479 -646
907 972 908 972
9 792 10 792
-913 -714 -912 -714
302 190 303 189
-721 -691 -720 -691
-133 -870 -132 -870
36...

output:


result:

FAIL Integer parameter [name=y] equals to -1001, violates the range [-1000, 1000] (test case 306, stdin, line 612)

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#305399#7903. Computational IntelligenceExplodingKonjacAC ✓276ms3844kbC++205.0kb2024-01-15 10:30:092024-01-15 10:30:10

answer

#include <bits/stdc++.h>
using namespace std;

using LL=long long;
using LD=long double;
using UI=unsigned int;
using ULL=unsigned long long;
constexpr LD EPS=1e-12;

#ifndef DADALZY
#define FILEIO(file) freopen(file".in","r",stdin),freopen(file".out","w",stdout)
#define LOG(...) [](auto...){}(__VA_ARGS__)
#else
#define FILEIO(file)
#define LOG(...) fprintf(stderr,__VA_ARGS__)
#endif

namespace Math
{

// A class for 2D vectors.
template<typename T>
struct Vector2d
{
	T x,y;
	Vector2d(): x(),y() {}
	Vector2d(const T &_x,const T &_y): x(_x),y(_y) {}
#define DEF_OP1(op) \
	Vector2d &operator op##=(const Vector2d &rhs) \
	{ return x op##= rhs.x,y op##= rhs.y,*this; } \
	Vector2d operator op(const Vector2d &rhs)const \
	{ return Vector2d(*this)op##=rhs; }
	DEF_OP1(+) DEF_OP1(-) DEF_OP1(*) DEF_OP1(/)
#undef DEF_OP1
	template<typename U>
	Vector2d &operator *=(U scale)
	{ return x*=scale,y*=scale,*this; }
	template<typename U>
	Vector2d &operator /=(U scale)
	{ return x/=scale,y/=scale,*this; }
	template<typename U>
	friend Vector2d operator *(U scale,const Vector2d &u)
	{ return Vector2d(u)*=scale; }
	template<typename U>
	friend Vector2d operator *(const Vector2d &u,U scale)
	{ return Vector2d(u)*=scale; }
	template<typename U>
	friend Vector2d operator /(const Vector2d &u,U scale)
	{ return Vector2d(u)/=scale; }
	auto proj(const Vector2d &u)const
	{ return (*this)*(dot(u,*this)/abs2(*this)); }
	template<typename U>
	auto trunc(U r)const
	{ auto l=abs(*this);return l?(*this)*(r/l):*this; }
	template<typename U>
	auto rotate(U t)const
	{ auto c=std::cos(t),s=std::sin(t);return Vector2d(x*c-y*s,x*s+y*c); }
	bool operator <(const Vector2d &rhs)const
	{ return x!=rhs.x?x<rhs.x:y<rhs.y; }
	bool operator ==(const Vector2d &rhs)const
	{ return x==rhs.x && y==rhs.y; }
	bool operator !=(const Vector2d &rhs)const
	{ return x!=rhs.x && y!=rhs.y; }
};
template<typename T>
auto cross(const Vector2d<T> &u,const Vector2d<T> &v)
{ return u.x*v.y-u.y*v.x; }
template<typename T>
auto dot(const Vector2d<T> &u,const Vector2d<T> &v)
{ return u.x*v.x+u.y*v.y; }
template<typename T>
auto abs(const Vector2d<T> &u)
{ return std::hypot(u.x,u.y); }
template<typename T>
auto abs2(const Vector2d<T> &u)
{ return u.x*u.x+u.y*u.y; }
template<typename T>
auto arg(const Vector2d<T> &u)
{ return std::atan2(u.y,u.x); }

} // namespace Math
using RVec=Math::Vector2d<LD>;

int T;
RVec u1,u2,v1,v2;

inline LD sqr(LD x) { return x*x; }
inline LD cub(LD x) { return x*x*x; }
inline LD det(LD a,LD b,LD c,LD d) { return a*d-b*c; }
inline int sgn(LD x) { return x>EPS?1:x<-EPS?-1:0; }

inline LD f(LD a,LD b,LD x)
{
	auto atanh_=[](LD x) {
		return atanh(clamp(x,-1.L,1.L));
	};
	LD a2=a*a,b2=b*b,x2=x*x,b3=b2*b,x3=x2*x;
	LD y=sqrt(b2+2*a*b*x+(1+a2)*x2),v=1+a2;
	LD res=
	  ((sgn(b3)?3*(-1+2*a2)*b3*atanh_((a*b+x+a2*x)/(sqrt(v)*y)):0)+
		   (sgn(b3)?18*b3*atanh_(sgn(x)?(-abs(b)+y)/(sqrt(v)*x):(a*abs(b))/(sqrt(1+a2)*b)):0)+
		   2*v*sqrt(v)*(v*x3+3*a*b2*y+6*b*v*x*y+
			  3*a*v*x2*y-(sgn(x)?3*v*x3*log(-b-a*x+y):0)))/(36*sqr(v)*sqrt(v));
	return res;
}
inline LD g(LD a,LD b,LD c,LD x)
{
	LD v=c+x*x,sv=sqrt(max(0.L,v));
	LD res=(sv*(3*b*x+2*a*v)-(sgn(c)?3*b*c*log(sv-x):0))/6;
	return res;
}

int main()
{
#ifndef DADALZY
	ios::sync_with_stdio(false);
	cin.tie(nullptr),cout.tie(nullptr);
#else
	freopen("input.in","r",stdin);
#endif
	cin>>T;
	cout<<setprecision(12)<<fixed;
	for(int o=1;o<=T;o++)
	{
		cin>>u1.x>>u1.y>>v1.x>>v1.y;
		cin>>u2.x>>u2.y>>v2.x>>v2.y;
		v1-=u1,v2-=u2;

		LD A1=v1.x,B1=-v2.x,C1=u1.x-u2.x,
		   A2=v1.y,B2=-v2.y,C2=u1.y-u2.y;
		LD ans=0;

		if(A1*B2==A2*B1)
		{
			if(!A1) swap(A1,A2),swap(B1,B2),swap(C1,C2);
			LD k=A2/A1,kk=1+sqr(k),c=sqr(C1)+sqr(C2)-sqr(C1+C2*k)/(1+sqr(k));
			auto trans=[&,d=(C1+C2*k)/(1+sqr(k))](const RVec &v) {
				return RVec(A1*v.x+B1*v.y+d,v.y);
			};
			auto calc=[&](const RVec &fr,const RVec &to)->LD {
				if(fr.x==to.x) return 0;
				LD a=(to.y-fr.y)/(to.x-fr.x),b=fr.y-fr.x*a;
				return g(a,b,c/kk,to.x)-g(a,b,c/kk,fr.x);
			};
			RVec p[4]={trans(RVec(0,0)),trans(RVec(1,0)),trans(RVec(1,1)),trans(RVec(0,1))};
			for(int i=0;i<4;i++)
				ans+=calc(p[i],p[(i+1)%4]);
			ans=abs(ans*sqrt(kk)/A1);
		}
		else
		{
			auto trans=[&](const RVec &v) {
				return RVec(A1*v.x+B1*v.y+C1,A2*v.x+B2*v.y+C2);
			};
			auto calc=[&](const RVec &fr,const RVec &to)->LD {
				if(fr.x==to.x) return 0;
				LD a=(to.y-fr.y)/(to.x-fr.x),b=fr.y-fr.x*a;
				return f(a,b,to.x)-f(a,b,fr.x);
			};
			RVec p[4]={trans(RVec(0,0)),trans(RVec(1,0)),trans(RVec(1,1)),trans(RVec(0,1))};
			LD mnx=INFINITY,mxx=-INFINITY,
			   mny=INFINITY,mxy=-INFINITY;
			for(int i=0;i<4;i++)
			{
				mnx=min(mnx,p[i].x),mxx=max(mxx,p[i].x);
				mny=min(mny,p[i].y),mxy=max(mxy,p[i].y);
			}
			if(mxy-mny>mxx-mnx)
				for(int i=0;i<4;i++) swap(p[i].x,p[i].y);
			for(int i=0;i<4;i++)
				ans+=calc(p[i],p[(i+1)%4]);
			LD k=A2*B1-A1*B2;
			ans=abs(ans*det(-B2/k,B1/k,A2/k,-A1/k));
		}
		cout<<ans<<'\n';
	}
	return 0;
}