QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#139413#4972. Stone SmoothingartcsWA 9ms4132kbC++171.8kb2023-08-13 12:40:012023-08-13 12:40:02

Judging History

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

  • [2023-08-13 12:40:02]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:4132kb
  • [2023-08-13 12:40:01]
  • 提交

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