QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#737322 | #7065. Triangle | icpc_zhzx034# | WA | 528ms | 3840kb | C++14 | 3.5kb | 2024-11-12 15:28:54 | 2024-11-12 15:28:54 |
Judging History
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'