QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#139413 | #4972. Stone Smoothing | artcs | WA | 9ms | 4132kb | C++17 | 1.8kb | 2023-08-13 12:40:01 | 2023-08-13 12:40:02 |
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 func(double mid, vector<double>& arr, int k)
{
lli need = 0;
for (int i=0;i<int(arr.size());i++)
{
double x = arr[i];
cout<<"x: "<<x<<endl;
cout<<"mid: "<<mid<<endl;
need += (lli)((x-180) / (mid-180));
if (need > k) return 0;
}
return (need <= k);
}
int main()
{
int n, k;
cin>>n>>k;
vector<Point> pts(n+2);
vector<double>angs(n);
for(int i=0; i<n; i++)
cin>>pts[i].x>>pts[i].y;
pts[n] = pts[0];
pts[n+1] = pts[1];
for(int i=0;i<n;i++)
angs[i] = 360 - pts[i+1].getAngle(pts[i], pts[i+2]);
double ini=180.0, fin=360.0;
for(int i = 0; i < 60; i++) {
double mid = (ini+fin) / 2.0;
if (func(mid, angs, k))
fin = mid;
else
ini = mid;
}
cout << setprecision(12) << fin << endl;
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 9ms
memory: 4132kb
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:
x: 180.336 mid: 270 x: 256.246 mid: 270 x: 192.078 mid: 270 x: 180.88 mid: 270 x: 180.078 mid: 270 x: 180.052 mid: 270 x: 180.377 mid: 270 x: 269.668 mid: 270 x: 180.02 mid: 270 x: 180.004 mid: 270 x: 180.02 mid: 270 x: 181.983 mid: 270 x: 236.876 mid: 270 x: 194.078 mid: 270 x: 195.283 mid: 270 x: ...
result:
wrong output format Expected double, but "x:" found