QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#139415#4972. Stone SmoothingartcsAC ✓1ms4160kbC++171.7kb2023-08-13 12:42:372023-08-13 12:42:41

Judging History

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

  • [2023-08-13 12:42:41]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:4160kb
  • [2023-08-13 12:42:37]
  • 提交

answer


#include <bits/stdc++.h>

using namespace std;

typedef long long int lli;

class Point {
    public:
        lli x, y;
        Point() {
            x = 0; y = 0;
        }
        Point(lli xx, lli yy) {
            x = xx;
            y = yy;
        }
        Point(const Point & o) {
            x = o.x;
            y = o.y;
        }
        lli dot(Point o) {
            return x*o.x+y*o.y;
        }
        lli cross(Point o) {
            return x*o.y-y*o.x;
        }
        Point operator+(const Point & o) {
            Point res(x+o.x,y+o.y);
            return res;
        }
        Point operator-(const Point & o) {
            Point res(x-o.x,y-o.y);
            return res;
        }
        double getAngle(Point a, Point c) {
            Point v1 = a-*this;
            Point v2 = c-*this;
            return atan2(v1.cross(v2), v1.dot(v2))*180/M_PI;
        }
};

int canDo(double tar, vector<double> & arr, int k) {
    lli need = 0;
    for (auto x : arr) {
        need += (lli)((x-180) / (tar-180));
        if (need > k) return 0;
    }

    return (need <= k);
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<Point> pts(n + 2);

    for (int i = 0; i < n; i++) {
        cin >> pts[i].x >> pts[i].y;
    }
    pts[n] = pts[0];
    pts[n+1] = pts[1];

    vector<double> angs(n);
    for (int i = 0; i < n; i++)
        angs[i] = 360 - pts[i+1].getAngle(pts[i], pts[i+2]);
    
    double lo = 180;
    double hi = 360;

    for(int i = 0; i < 60; i++) {
        double mid = (lo+hi) / 2;
        if (canDo(mid, angs, k)) 
            hi = mid;
        else
            lo = mid;
    }

    cout << setprecision(12) << hi << endl;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

25 86753
-99969 28872
-99728 69167
-99386 98018
-93052 99489
-67698 99930
-52987 99960
-18803 99983
88963 99958
99980 99883
99896 17395
99839 -24236
99806 -47084
99772 -66130
98709 -95321
94975 -97568
89299 -99299
73313 -99767
71486 -99799
-6077 -99924
-58379 -99853
-88832 -99582
-92680 -99133
-9800...

output:

180.004149166

result:

ok found '180.0041492', expected '180.0041492', error '0.0000000'

Test #2:

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

input:

23 86753
-99821 92789
-96579 99143
-95208 99716
-90607 99981
-18875 99971
72366 99710
84987 99044
96940 96984
99433 94929
99953 79373
99911 4782
99700 -93051
99631 -95990
99337 -96401
96739 -98818
84059 -99420
72670 -99769
5249 -99929
-51461 -99956
-73223 -99758
-87250 -99427
-97136 -96916
-99998 -9...

output:

180.004149282

result:

ok found '180.0041493', expected '180.0041493', error '0.0000000'

Test #3:

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

input:

300 100
299 89401
298 88804
297 88209
296 87616
295 87025
294 86436
293 85849
292 85264
291 84681
290 84100
289 83521
288 82944
287 82369
286 81796
285 81225
284 80656
283 80089
282 79524
281 78961
280 78400
279 77841
278 77284
277 76729
276 76176
275 75625
274 75076
273 74529
272 73984
271 73441
27...

output:

183.394421675

result:

ok found '183.3944217', expected '183.3944217', error '0.0000000'

Test #4:

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

input:

300 10000
299 89401
298 88804
297 88209
296 87616
295 87025
294 86436
293 85849
292 85264
291 84681
290 84100
289 83521
288 82944
287 82369
286 81796
285 81225
284 80656
283 80089
282 79524
281 78961
280 78400
279 77841
278 77284
277 76729
276 76176
275 75625
274 75076
273 74529
272 73984
271 73441
...

output:

180.035850338

result:

ok found '180.0358503', expected '180.0358503', error '0.0000000'

Test #5:

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

input:

300 1000000
299 89401
298 88804
297 88209
296 87616
295 87025
294 86436
293 85849
292 85264
291 84681
290 84100
289 83521
288 82944
287 82369
286 81796
285 81225
284 80656
283 80089
282 79524
281 78961
280 78400
279 77841
278 77284
277 76729
276 76176
275 75625
274 75076
273 74529
272 73984
271 7344...

output:

180.000359949

result:

ok found '180.0003599', expected '180.0003599', error '0.0000000'

Test #6:

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

input:

300 1000000000
299 89401
298 88804
297 88209
296 87616
295 87025
294 86436
293 85849
292 85264
291 84681
290 84100
289 83521
288 82944
287 82369
286 81796
285 81225
284 80656
283 80089
282 79524
281 78961
280 78400
279 77841
278 77284
277 76729
276 76176
275 75625
274 75076
273 74529
272 73984
271 7...

output:

180.00000036

result:

ok found '180.0000004', expected '180.0000004', error '0.0000000'

Test #7:

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

input:

600 100
299 89401
298 88804
297 88209
296 87616
295 87025
294 86436
293 85849
292 85264
291 84681
290 84100
289 83521
288 82944
287 82369
286 81796
285 81225
284 80656
283 80089
282 79524
281 78961
280 78400
279 77841
278 77284
277 76729
276 76176
275 75625
274 75076
273 74529
272 73984
271 73441
27...

output:

183.29501591

result:

ok found '183.2950159', expected '183.2950159', error '0.0000000'

Test #8:

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

input:

600 10000
299 89401
298 88804
297 88209
296 87616
295 87025
294 86436
293 85849
292 85264
291 84681
290 84100
289 83521
288 82944
287 82369
286 81796
285 81225
284 80656
283 80089
282 79524
281 78961
280 78400
279 77841
278 77284
277 76729
276 76176
275 75625
274 75076
273 74529
272 73984
271 73441
...

output:

180.035730138

result:

ok found '180.0357301', expected '180.0357301', error '0.0000000'

Test #9:

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

input:

600 1000000
299 89401
298 88804
297 88209
296 87616
295 87025
294 86436
293 85849
292 85264
291 84681
290 84100
289 83521
288 82944
287 82369
286 81796
285 81225
284 80656
283 80089
282 79524
281 78961
280 78400
279 77841
278 77284
277 76729
276 76176
275 75625
274 75076
273 74529
272 73984
271 7344...

output:

180.000359897

result:

ok found '180.0003599', expected '180.0003599', error '0.0000000'

Test #10:

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

input:

600 100000000
299 89401
298 88804
297 88209
296 87616
295 87025
294 86436
293 85849
292 85264
291 84681
290 84100
289 83521
288 82944
287 82369
286 81796
285 81225
284 80656
283 80089
282 79524
281 78961
280 78400
279 77841
278 77284
277 76729
276 76176
275 75625
274 75076
273 74529
272 73984
271 73...

output:

180.0000036

result:

ok found '180.0000036', expected '180.0000036', error '0.0000000'

Test #11:

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

input:

4 4
-1 1
1 1
1 -1
-1 -1

output:

225

result:

ok found '225.0000000', expected '225.0000000', error '0.0000000'