QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#340267 | #8214. Huge Oil Platform | ucup-team191# | TL | 5ms | 4180kb | C++23 | 4.2kb | 2024-02-28 20:04:50 | 2024-02-28 20:04:52 |
Judging History
answer
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)
template<class T> int sgn(T x) {return (x>0)-(x<0);}
template<class T>
struct Point {
typedef Point P;
T x,y;
explicit Point(T x=0,T y=0) : x(x), y(y) {}
bool operator<(P p) const {return tie(x,y)<tie(p.x,p.y);}
bool operator==(P p) const {return tie(x,y)==tie(p.x,p.y);}
P operator+(P p) const {return P(x+p.x,y+p.y);}
P operator-(P p) const {return P(x-p.x,y-p.y);}
P operator*(T d) const {return P(x*d,y*d);}
P operator/(T d) const {return P(x/d,y/d);}
T dot(P p) const {return x*p.x+y*p.y;}
T cross(P p) const {return x*p.y-y*p.x;}
T cross(P a,P b) const {return (a-*this).cross(b-*this);}
T dist2() const {return x*x+y*y;}
ld dist() const {return sqrt((ld)dist2());}
ld angle() const {return atan2(y,x);}
P unit() const {return *this/dist();}
P perp() const {return P(-y,x);}
P normal() const {return perp().unit();}
P rotate(double a) const {return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a));}
friend ostream& operator<<(ostream&os,P p) {
return os << "(" << p.x << "," << p.y << ")";
}
};
typedef Point<ld> P;
P lt(const P&p0,const P&p1,const P&q0,const P&q1,const P&r)
{
P dp=p1-p0,dq=q1-q0,num(dp.cross(dq),dp.dot(dq));
return q0+P((r-p0).cross(num),(r-p0).dot(num))/dp.dist2();
}
const int N=410,MOD=1e9+7,M=1<<9;
const char en='\n';
const ll LLINF=1ll<<60;
const ld eps=1e-8; //per se poveca za najvise eps
int n;
pair<ld,ld> seg[2][M*2+10];
pair<P,int> h[N];
ld cuan;
pair<ld,ld> mer(pair<ld,ld> a,pair<ld,ld> b)
{
return {a.x+b.x,max(a.y,a.x+b.y)};
}
void upd(int i,int j,ld x)
{
seg[j][i+=M].x+=x;
seg[j][i].y=max(0.L,seg[j][i].x);
for (i/=2;i;i/=2) seg[j][i]=mer(seg[j][i*2],seg[j][i*2+1]);
}
pair<ld,ld> ge(int l,int r,int j,int lo=0,int hi=M,int i=1)
{
if (lo>=l && hi<=r) return seg[j][i];
if (lo>=r || hi<=l) return {0,0};
int mid=(lo+hi)/2;
return mer(ge(l,r,j,lo,mid,i*2),ge(l,r,j,mid,hi,i*2+1));
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
ld ma=0;
for (int i=0;i<n;++i)
{
cin>>h[i].x.x>>h[i].x.y>>h[i].y;
ma=max(ma,ld(h[i].y));
}
for (int i=0;i<n;++i) for (int j=i+1;j<n;++j)
{
vector<pair<pair<ld,ld>,int>> vec,man;
vector<ld> vxman,vxvec;
P p0=h[i].x,p1=h[j].x,q0=P(0,0),q1=P((h[i].x-h[j].x).dist(),0);
for (int k=0;k<n;++k)
{
P nov=lt(p0,p1,q0,q1,h[k].x);
if (nov.x<0) vxman.pb(-nov.x);
if (nov.x>q1.x) vxvec.pb(nov.x-q1.x);
if (nov.y>-eps) vec.pb({{nov.y,nov.x},h[k].y});
if (nov.y<eps) man.pb({{-nov.y,nov.x},h[k].y});
}
sort(all(vec));
sort(all(man));
sort(all(vxman));
vxman.erase(unique(all(vxman)),vxman.end());
sort(all(vxvec));
vxvec.erase(unique(all(vxvec)),vxvec.end());
//clear starts
for (int i=0;i<2*M;++i) seg[0][i]=seg[1][i]={0,0};
cuan=-2*q1.x;
for (int i=0;i<(int)vxman.size();++i)
{
ld dif=vxman[i];
if (i) dif-=vxman[i-1];
upd(i,0,-2*dif);
}
for (int i=0;i<(int)vxvec.size();++i)
{
ld dif=vxvec[i];
if (i) dif-=vxvec[i-1];
upd(i,1,-2*dif);
}
//clear ends
for (auto x: vec)
{
if (x.x.y<0)
{
upd(lower_bound(all(vxman),-x.x.y)-vxman.begin(),0,x.y);
}
else if (x.x.y>q1.x)
{
upd(lower_bound(all(vxvec),x.x.y-q1.x)-vxvec.begin(),1,x.y);
}
else cuan+=x.y;
ma=max(ma,cuan-2*x.x.x+seg[0][1].y+seg[1][1].y);
}
//clear starts
for (int i=0;i<2*M;++i) seg[0][i]=seg[1][i]={0,0};
cuan=-2*q1.x;
for (int i=0;i<(int)vxman.size();++i)
{
ld dif=vxman[i];
if (i) dif-=vxman[i-1];
upd(i,0,-2*dif);
}
for (int i=0;i<(int)vxvec.size();++i)
{
ld dif=vxvec[i];
if (i) dif-=vxvec[i-1];
upd(i,1,-2*dif);
}
//clear ends
for (auto x: man)
{
if (x.x.y<0)
{
upd(lower_bound(all(vxman),-x.x.y)-vxman.begin(),0,x.y);
}
else if (x.x.y>q1.x)
{
upd(lower_bound(all(vxvec),x.x.y-q1.x)-vxvec.begin(),1,x.y);
}
else cuan+=x.y;
ma=max(ma,cuan-2*x.x.x+seg[0][1].y+seg[1][1].y);
}
}
cout<<fixed<<setprecision(10)<<ma<<en;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4112kb
input:
2 1 1 1 3 3 1
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4180kb
input:
3 4 5 5 4 6 7 1 3 8
output:
10.1005050634
result:
ok found '10.1005051', expected '10.1005051', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3888kb
input:
2 0 0 1 1000000 1000000 1000000000
output:
1000000000.0000000000
result:
ok found '1000000000.0000000', expected '1000000000.0000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 5ms
memory: 3948kb
input:
20 328 207 21 365 145 188 347 79 41 374 335 699 288 250 97 32 267 131 296 332 434 2 91 36 139 43 21 26 455 696 57 135 410 14 500 396 255 181 646 103 114 593 309 351 787 207 316 138 440 416 806 413 349 695 413 201 501 455 396 442
output:
6092.4427126238
result:
ok found '6092.4427126', expected '6092.4427126', error '0.0000000'
Test #5:
score: 0
Accepted
time: 5ms
memory: 4004kb
input:
20 38 207 766 202 485 964 257 466 900 205 486 738 166 53 716 61 94 881 252 165 182 63 292 612 225 278 242 224 242 566 381 196 702 56 494 997 268 288 884 379 227 3 357 271 975 55 73 678 260 55 623 399 369 515 116 354 580 404 239 950
output:
11878.2573128275
result:
ok found '11878.2573128', expected '11878.2573128', error '0.0000000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3944kb
input:
20 249 215 320 38 48 229 457 366 56 36 142 186 44 96 935 97 190 143 215 218 123 116 486 291 304 232 463 429 297 29 479 475 97 97 198 405 69 395 121 381 121 926 137 197 972 410 91 218 87 421 737 117 390 144 319 287 170 353 302 754
output:
5573.2558969326
result:
ok found '5573.2558969', expected '5573.2558969', error '0.0000000'
Test #7:
score: 0
Accepted
time: 5ms
memory: 3952kb
input:
20 474 215 66 376 120 6 367 259 211 362 293 34 416 407 554 133 292 894 171 278 871 459 187 674 383 192 980 352 78 899 83 27 684 138 185 709 357 234 359 390 241 40 418 124 161 258 348 462 408 59 851 110 184 668 28 447 761 20 131 367
output:
8510.5956178834
result:
ok found '8510.5956179', expected '8510.5956179', error '0.0000000'
Test #8:
score: -100
Time Limit Exceeded
input:
400 979422 264252 76260 922920 334464 58710 87057 798078 39652 602478 649867 49073 388746 161788 44501 727471 373113 28061 944959 505744 22145 191465 164645 49421 102241 771049 65953 44911 762286 34082 112779 537040 98117 688054 585935 53647 391845 931395 55355 788464 698271 91449 984533 409449 8331...