第八个数据点过不去
查看原帖
第八个数据点过不去
286047
OldAtaraxia楼主2020/6/9 17:22

是在找不到哪里有问题了,但是第八个数据点死活过不去

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const double pi = 3.141592653;

int N;
P points[10];
int R[10];
bool vis[10];
long double ans = 0;
int X0, Y0, Xm, Ym;



long double dis(int x1,int y1, int x2, int y2){
    return sqrt( 1.0 * (x1 - x2) * (x1 - x2) + 1.0 * (y1 - y2) * (y1 - y2)) ;
}

void dfs(int p, int cnt, long double s) {
    if(p != 0){
        long double r = min(Ym - points[p].second, min(Xm - points[p].first, min(points[p].first, points[p].second)));
        
        for (int i = 1; i <= N; i++){
            if(vis[i] && i != p ){
                r = min(r, max(dis(points[p].first, points[p].second, points[i].first, points[i].second) - R[i], (long double)0.0));
            }
        }
        R[p] = r;
        s += pi * r * r;
    }
    if (cnt == N) {
        
        if(s > ans)
            ans = s;
        return;
    }
    for (int i = 1; i <= N; i++){
        if (!vis[i]){
            vis[i] = 1;
            dfs(i, cnt + 1, s);
            vis[i] = 0;
        }
    }
} 


int main(){
    ios::sync_with_stdio(0);
    cin >> N;
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    long double ss = abs((x2 - x1) * (y2 - y1));
    X0 = min(x1, x2); Y0 = min(y1, y2);
    Xm = max(x1, x2);
    Ym = max(y1, y2);
    Xm -= X0;
    Ym -= Y0;
    for (int i = 1; i <= N; i++){
        cin >> points[i].first >> points[i].second;
        points[i].first -= X0;
        points[i].second -= Y0;
    }
    dfs(0, 0, 0.0);
    cout << (int)(ss - ans + 0.5) << endl;
    
    
    return 0;
} 
2020/6/9 17:22
加载中...