QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#265908 | #7734. Intersection over Union | ucup-team052 | WA | 1443ms | 3756kb | C++23 | 2.9kb | 2023-11-25 22:20:11 | 2023-11-25 22:20:11 |
Judging History
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'