QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#737322#7065. Triangleicpc_zhzx034#WA 528ms3840kbC++143.5kb2024-11-12 15:28:542024-11-12 15:28:54

Judging History

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

  • [2024-11-12 15:28:54]
  • 评测
  • 测评结果:WA
  • 用时:528ms
  • 内存:3840kb
  • [2024-11-12 15:28:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define fi first
#define se second
#define mk make_pair
#define eb emplace_back
#define rep(i,l,r) for(int i=(l); i<=(r); ++i)
#define rep_(i,l,r) for(int i=(l); i>=(r); --i)
typedef long long lr;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
constexpr int mod1=998244353,mod2=1e9+7;
constexpr db pi=3.141592653589793,eps=1e-9;
constexpr int inf32=0x3f3f3f3f,Inf32=0xc0c0c0c0;
constexpr lr inf64=0x3f3f3f3f3f3f3f3f,Inf64=0xc0c0c0c0c0c0c0c0;
template<typename T>il T Max(T x,T y) { return (x>y)? x:y; }
template<typename T>il T Min(T x,T y) { return (x<y)? x:y; }
template<typename T>il T gcd(T x,T y) { return (!y)? x:gcd(y,x%y); }
template<typename T>il T Abs(T x) { return (x>0)? x:(-x); }
template<typename T>il T Rnd(T l,T r,mt19937_64 &eng)
{
	uniform_int_distribution<T> uid(l,r);
	return uid(eng);
}
mt19937_64 eng(chrono::high_resolution_clock::now().time_since_epoch().count());
constexpr int N=524300;
il db cross(db xa,db ya,db xb,db yb,db xc,db yc) { return Abs((xa-xc)*(yb-yc)-(xb-xc)*(ya-yc)); }
db tmp;
il bool chk(int xa,int ya,int xb,int yb,int x,int y)
{
	if((x<xa&&x<xb)||(x>xa&&x>xb)||(y<ya&&y<yb)||(y>ya&&y>yb))
		return 0;
	return (lr)(x-xa)*(yb-ya)==(lr)(y-ya)*(xb-xa);
}
il void calc(int xa,int ya,int xb,int yb,int xl,int yl,int xr,int yr)
{
	if(xl==xr)
	{
		db l=yl,r=yr,mid,ax=0,ay=0;
		while(Abs(r-l)>eps)
		{
			mid=(l+r)*0.5;
			db xc=xl,yc=mid;
			if(cross(xa,ya,xb,yb,xc,yc)*2>=tmp)
				ax=xc,ay=yc,(l<r)? (r=mid-eps):(r=mid+eps);
			else
				(l<r)? (l=mid+eps):(l=mid-eps);
		}
		cout<<setiosflags(ios::fixed)<<setprecision(6)<<ax<<' '<<ay<<'\n';
		return;
	}
	db l=xl,r=xr,mid,ax=0,ay=0;
	while(Abs(r-l)>eps)
	{
		mid=(l+r)*0.5;
		db xc=mid,yc=(yl*(xr-xc)+yr*(xc-xl))/(xr-xl);
		if(cross(xa,ya,xb,yb,xc,yc)*2>=tmp)
			ax=xc,ay=yc,(l<r)? (r=mid-eps):(r=mid+eps);
		else
			(l<r)? (l=mid+eps):(l=mid-eps);
	}
	cout<<setiosflags(ios::fixed)<<setprecision(6)<<ax<<' '<<ay<<'\n';
}
int xa,ya,xb,yb,xc,yc,xp,yp;
il void Solve()
{
	cin>>xa>>ya>>xb>>yb>>xc>>yc>>xp>>yp,tmp=cross(xa,ya,xb,yb,xc,yc);
	if(chk(xa,ya,xb,yb,xp,yp))
	{
		if(xa==xb)
		{
			int ap=Abs(yp-ya),bp=Abs(yp-yb);
			if(ap>bp)
				return calc(xa,ya,xp,yp,xa,ya,xc,yc);
			else
				return calc(xb,yb,xp,yp,xb,yb,xc,yc);
		}
		int ap=Abs(xp-xa),bp=Abs(xp-xb);
		if(ap>bp)
			return calc(xa,ya,xp,yp,xa,ya,xc,yc);
		else
			return calc(xb,yb,xp,yp,xb,yb,xc,yc);
	}
	if(chk(xa,ya,xc,yc,xp,yp))
	{
		if(xa==xc)
		{
			int ap=Abs(yp-ya),cp=Abs(yp-yc);
			if(ap>cp)
				return calc(xa,ya,xp,yp,xa,ya,xb,yb);
			else
				return calc(xc,yc,xp,yp,xc,yc,xb,yb);
		}
		int ap=Abs(xp-xa),cp=Abs(xp-xc);
		if(ap>cp)
			return calc(xa,ya,xp,yp,xa,ya,xb,yb);
		else
			return calc(xc,yc,xp,yp,xc,yc,xb,yb);
	}
	if(chk(xb,yb,xc,yc,xp,yp))
	{
		if(xb==xc)
		{
			int bp=Abs(yp-yb),cp=Abs(yp-yc);
			if(bp>cp)
				return calc(xb,yb,xp,yp,xb,yb,xa,ya);
			else
				return calc(xc,yc,xp,yp,xc,yc,xa,ya);
		}
		int bp=Abs(xp-xb),cp=Abs(xp-xc);
		if(bp>cp)
			return calc(xb,yb,xp,yp,xb,yb,xa,ya);
		else
			return calc(xc,yc,xp,yp,xc,yc,xa,ya);
	}
	cout<<"-1\n";
}
int main()
{
#ifdef LOCAL
	string fpre="test",isuf="in",osuf="out";
	assert(freopen((fpre+"."+isuf).c_str(),"r",stdin));
	assert(freopen((fpre+"."+osuf).c_str(),"w",stdout));
#endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--)
		Solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3712kb

input:

2
0 0 1 1 1 0 1 0
0 0 1 1 1 0 2 0

output:

0.500000 0.500000
-1

result:

ok 3 numbers

Test #2:

score: -100
Wrong Answer
time: 528ms
memory: 3840kb

input:

999966
9456 15557 18451 3957 6242 20372 9855 5351
30245 31547 9979 4703 25914 19144 26670 11383
13855 0 24614 0 15860 11017 12445 0
27870 17680 4219 3554 9129 29072 28316 17893
3249 27269 12754 4923 31746 16860 14894 21576
6846 0 1915 0 25023 28721 10508 0
10110 11862 23224 10373 17715 8212 29474 11...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
21424.681479 13086.053911
-1
-1
18711.237990 10162.376377
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
28212.952135 245.817786
-1
-1
-1
-1
-1
-1
-1
-1
22604.575302 14546.128716
-1
-1
11557.346522 4668.209790
-1
-1
19488.201031 725.306...

result:

wrong answer 42645th numbers differ - expected: '18745.0000000', found: '0.0000000', error = '1.0000000'