50ptsTLE,不求AC,只求70pts
  • 板块P1433 吃奶酪
  • 楼主asd890123
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/4/29 20:07
  • 上次更新2024/4/29 22:07:43
查看原帖
50ptsTLE,不求AC,只求70pts
1074084
asd890123楼主2024/4/29 20:07
#include <math.h>
#include <iomanip>
#include <iostream>
#include <algorithm>

class pos{public:double x,y;};

template <typename T>
T sq(T a){return a * a;}
bool operator<(pos a,pos b){return a.x != b.x ? a.x < b.x : a.y < b.y;}
double dist(pos a,pos b){return sqrt(sq(a.x - b.x) + sq(a.y - b.y));}
std::istream &operator>>(std::istream &is,pos &a){is >> a.x >> a.y;return is;}

int main(){
    
    std::ios::sync_with_stdio(0);
    std::cin.tie(0),std::cout.tie(0);
    
    int n;
    pos a[20];
    double cnt,ans = 0x7fffffff;
    
    std::cin >> n;
    a[0] = (pos){0,0};
    for (int i = 1;i <= n;i++) std::cin >> a[i];
    std::sort(a + 1,a + 1 + n);
    do{
        
        cnt = 0;
        for (int i = 1;i <= n;i++)
            cnt += dist(a[i],a[i - 1]);
        ans = std::min(ans,cnt);
        
    }while (std::next_permutation(a + 1,a + 1 + n));
    std::cout << std::fixed << std::setprecision(2) << ans << std::endl;
    
    return 0;
}

深基第10章说70%的数据n<=11,但是为什么我用全排列只有50分,n!应该可以过n<=11吧

2024/4/29 20:07
加载中...