QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#139415 | #4972. Stone Smoothing | artcs | AC ✓ | 1ms | 4160kb | C++17 | 1.7kb | 2023-08-13 12:42:37 | 2023-08-13 12:42:41 |
Judging History
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;
}
详细
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'