QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#344602#8214. Huge Oil PlatformSolitaryDream#TL 1ms4080kbC++172.3kb2024-03-04 20:18:552024-03-04 20:18:55

Judging History

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

  • [2024-03-04 20:18:55]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4080kb
  • [2024-03-04 20:18:55]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
typedef long double db;
typedef long long ll;
struct Point {
    ll x,y;
    Point operator -(const Point &s) const{
        return {x-s.x,y-s.y};
    }
    db Len() const{
        return hypot(x,y);
    }
};
ll det(Point a,Point b) {
    return a.x*b.y-a.y*b.x;
}
ll dot(Point a,Point b) {
    return a.x*b.x+a.y*b.y;
}
const int N=405;
Point a[N];
int w[N];
vector<db> X;
struct node {
    db ans,lmx,rmx,sum;
} T[N<<2];
#define ls p<<1
#define rs p<<1|1
#define lson L,mid,ls
#define rson mid+1,R,rs
void build(int L,int R,int p) {
    T[p]={0,0,0,-(X[R]-X[L])*2};
    if(L==R) return ;
    int mid=L+R>>1;
    build(lson);
    build(rson);
}
void Insert(int L,int R,int p,int x,int v) {
    if(L==R) {
        T[p].ans+=v;
        T[p].lmx+=v;
        T[p].rmx+=v;
        T[p].sum+=v;
        return ;
    }
    int mid=L+R>>1;
    if(x<=mid) Insert(lson,x,v);
    else Insert(rson,x,v);
    db d=(X[mid+1]-X[mid])*2;
    T[p].ans=max({T[ls].ans,T[rs].ans,T[ls].rmx+T[rs].lmx-d});
    T[p].lmx=max(T[ls].lmx,T[ls].sum+T[rs].lmx-d);
    T[p].rmx=max(T[rs].rmx,T[rs].sum+T[ls].rmx-d);
    T[p].sum=T[ls].sum+T[rs].sum-d;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(12);
    int n;
    cin >> n;
    db res=0;
    FOR(i,1,n) {
        int x,y;
        cin >> x >> y >> w[i];
        a[i]={x,y};
        res=max(res,(db)w[i]);
    }
    FOR(i,1,n) FOR(j,1,n) if(i!=j) {
        vector<tuple<db,db,int>> vec;
        X.clear();
        FOR(k,1,n) if(det(a[j]-a[i],a[k]-a[i])>=0) {
            db y=det(a[j]-a[i],a[k]-a[i])/(a[j]-a[i]).Len();
            db x=dot(a[j]-a[i],a[k]-a[i])/(a[j]-a[i]).Len();
            X.push_back(x);
            vec.push_back({y,x,w[k]});
        }
        sort(X.begin(),X.end());
        X.erase(unique(X.begin(),X.end()),X.end());
        sort(vec.begin(),vec.end());
        build(0,X.size()-1,1);
        for(auto [y,x,v]: vec) {
            int p=lower_bound(X.begin(),X.end(),x)-X.begin();
            // cerr << i << ' ' << j << ' ' << v << endl;
            Insert(0,X.size()-1,1,p,v);
            res=max(res,T[1].ans-y*2);
        }
    }
    cout << res << '\n';
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 4008kb

input:

2
1 1 1
3 3 1

output:

1.000000000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3912kb

input:

3
4 5 5
4 6 7
1 3 8

output:

10.100505063388

result:

ok found '10.1005051', expected '10.1005051', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

2
0 0 1
1000000 1000000 1000000000

output:

1000000000.000000000000

result:

ok found '1000000000.0000000', expected '1000000000.0000000', error '0.0000000'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3864kb

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.442712623783

result:

ok found '6092.4427126', expected '6092.4427126', error '0.0000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3924kb

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.257312827460

result:

ok found '11878.2573128', expected '11878.2573128', error '0.0000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 4080kb

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.255896932630

result:

ok found '5573.2558969', expected '5573.2558969', error '0.0000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3996kb

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.595617883409

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...

output:


result: