QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#863789#3001. Piece of CakeisWFnoya#TL 1ms4224kbC++263.4kb2025-01-19 22:26:032025-01-19 22:26:05

Judging History

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

  • [2025-01-19 22:26:05]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4224kb
  • [2025-01-19 22:26:03]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std ;
#define vec point
typedef long double db ; //卡精度就换long double,不过long double很慢
const db eps = 1e-9 ; //调参
const db pi = acos(-1.0) ;
const db inf = 40000 ;
int sgn(db x)
{
    if(x < -eps) return -1 ;
    else if (x > eps)  return 1 ;
    else return 0 ;
}
int cmp(db x , db y)
{
    return sgn(x - y) ;
}
void print(int num , db x)
{
    cout << fixed << setprecision(num) << x << '\n' ;
}
struct point
{
    db x , y ;
    point(){}
    point(db x2 , db y2)
    {
        x = x2 , y = y2 ;
    }
    void input()
    {
        db x2 , y2 ;
        cin >> x2 >> y2 ;
        x = x2 ;
        y = y2 ;
    }
    point operator + (const point& s)const{return (point){x + s.x , y + s.y} ;}
    point operator - (const point& s)const{return (point){x - s.x , y - s.y} ;}
    point operator * (const db& k)const{return (point){x * k , y * k} ;}
    point operator / (const db& k)const{return (point){x / k , y / k} ;}
    db operator * (const point &a) const {return x*a.x+y*a.y;} //Dot
    db operator ^ (const point &a) const {return x*a.y-y*a.x;} //Cross
    bool operator < (point b) const
    {
        return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x ;
    }
    bool equal(point p2)
    {
        return cmp(x , p2.x) == 0 && cmp(y , p2.y) == 0 ;
    }
    db get_angle(){return atan2(y , x) ;} //极角
    int getP() const{return sgn(y) == 1 || (sgn(y) == 0 && sgn(x) == -1) ;}
    db sq(db x) {return x * x ;}
    db dis(point p) //很吃精度,可能需要1e-10或更小的eps
    {
        return sqrtl(sq(x - p.x) + sq(y - p.y)) ; //check sqrt or sqrtl
    }
    db len()
    {
        return sqrtl(sq(x) + sq(y)) ;
    }
    db len2()
    {
        return sq(x) + sq(y) ;
    }
    point unit()
    {
        db w = len() ;
        return (point){x / w , y / w} ;
    }
    vec rotate_left()  //向量逆时针旋转90度
    {
        return vec(-y , x) ;
    }
    vec rotate_right()  //向量顺时针旋转90度
    {
        return vec(y , -x) ;
    }
    point move(db r) //原点沿该点代表的向量方向移动r
    {
        db l = len() ;
        if(sgn(l) == 0)  return *this ;
        else  return point(x * r / l , y * r / l) ;
    }
    vec rotate(db ang) //ang是弧度制,逆时针旋转
    {
        return vec({x * cos(ang) - y * sin(ang) , y * cos(ang) + x * sin(ang)}) ;
    }
} ;
db cross(vec s , vec t){return s.x * t.y - s.y * t.x ;} // 叉积
db fac[3000] ;
db C(int n , int m)
{
    if(n <= m)  return 1.0 ;
    return fac[n] / fac[m] / fac[n - m] ;
}
void solve()
{
    fac[0] = 1 ;
    for(int i = 1 ; i < 3000 ; i ++)  fac[i] = fac[i - 1] * i ;

    int n , k ;
    cin >> n >> k ;
    vector<point> p(n) ;
    for(int i = 0 ; i < n ; i ++)  p[i].input() ;
    reverse(p.begin() , p.end()) ;
    db ans = 0 ;
    for(int i = 0 ; i < n ; i ++)
        for(int j = i + 1 ; j < n ; j ++)
        {
            db c = cross(p[i] , p[j]) ;
            int cnt = n - (j - i + 1) ;
            if(cnt >= k - 2)        ans += c * C(cnt , k - 2) / C(n , k) ;
            cnt = j - i - 1 ;
            if(cnt >= k - 2)  ans -= c * C(cnt , k - 2) / C(n , k) ;
        }
    cout << fixed << setprecision(20) << ans / 2 << '\n' ;
}
int main()
{
    std::ios::sync_with_stdio(false) , cin.tie(0) ;

    int T = 1 ;
    // cin >> T ;
    while (T --)  solve() ;
    return 0 ;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 3
-5.236334 -8.519438
-9.987847 -0.492878
-9.994555 0.329962

output:

1.92794639622000000406

result:

ok found '1.9279464', expected '1.9279464', error '0.0000000'

Test #2:

score: -100
Time Limit Exceeded

input:

2496 3
-9.999961 0.028130
-9.999655 0.083151
-9.999641 0.084830
-9.999572 0.092537
-9.999474 0.102653
-9.999366 0.112678
-9.999329 0.115862
-9.998360 0.181104
-9.998033 0.198381
-9.997191 0.237035
-9.995264 0.307754
-9.993680 0.355494
-9.992454 0.388414
-9.992180 0.395407
-9.992030 0.399190
-9.99086...

output:


result: