QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#564564#7184. Transport Pluseskingmessi#WA 0ms3940kbC++203.9kb2024-09-15 09:59:432024-09-15 09:59:43

Judging History

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

  • [2024-09-15 09:59:43]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3940kb
  • [2024-09-15 09:59:43]
  • 提交

answer

// Har Har Mahadev
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x) 
#define btz(x) __builtin_ctz(x)
using namespace std;

using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;

const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
  
int power( int N, int M){
    int power = N, sum = 1;
    if(N == 0) sum = 0;
    while(M > 0){if((M & 1) == 1){sum *= power;}
    power = power * power;M = M >> 1;}
    return sum;
}
 
void solve()
{
    int n,k; 
    cin >> n >> k;
    int x1,x2,y1,y2;
    cin >> x1 >> y1;
    cin >> x2 >> y2;
    vector<int> x(n),y(n);
    repin{
        cin >> x[i] >> y[i];
    }
    vi cl;
    cl.pb(0);
    int dis = min(abs(x[0]-x2),abs(y[0]-y2));
    rep(i,1,n){
        int d = min(abs(x[i]-x2),abs(y[i]-y2));
        if(d < dis){
            dis = d;
            cl.clear();
            cl.pb(i);
        }
        else if(d == dis){
            cl.pb(i);
        }
    }
    double ans = sqrt(1.00*abs(x2-x1)*abs(x2-x1) + abs(y2-y1)*abs(y2-y1));
    bool w = 0;
    int d = INF;
    int p = 0;
    for(auto i : cl){
        if(min(abs(x[i]-x1),abs(y[i]-y1)) < d){
            p = i;
            d = min(abs(x[i]-x1),abs(y[i]-y1));
        }
    }
    if(1.0*d + dis + k < ans){
        ans = d + dis + k;
        w = 1;
    }
    int d1 = INF;
    int pt = 0;
    repin{
        if(min(abs(x[i]-x1),abs(y[i]-y1)) < d1){
            pt = i;
            d1 = min(abs(x[i]-x1),abs(y[i]-y1));
        }
    }
    // cout << d << " " << d1 << " " << dis << "gi\n";
    if(1.0*d1 + dis + 2*k < ans){
        ans = d1 + dis + 2*k;
        w = 2;
    }
    cout << ans << "\n";
    if(w == 0){
        cout << 1 << "\n";
        cout << 0 << " " << x2 << " " << y2 << "\n";return;
    }
    if(w == 1){
        cout << 3 << "\n";
        if(abs(x[p] - x1) < abs(y[p] - y1)){
            cout << 0 << " " << x[p] << " " << y1 << "\n";
        }
        else cout << 0 << " " << x1 << " " << y[p] << "\n";
        if(abs(x[p] - x2) < abs(y[p] - y2)){
            cout << p+1 << " " << x[p] << " " << y2 << "\n";
        }
        else cout << p+1 << " " << x2 << " " << y[p] << "\n";
        cout << 0 << " " << x2 << " " << y2 << "\n";return;
    }
    if(w == 2){
        cout << 4 << "\n";
        if(abs(x[pt] - x1) < abs(y[pt] - y1)){
            cout << 0 << " " << x[pt] << " " << y1 << "\n";
        }
        else cout << 0 << " " << x1 << " " << y[pt] << "\n";
        cout << 1+pt << " " << x[pt] << " " << y[p] << "\n";
        if(abs(x[p] - x2) < abs(y[p] - y2)){
            cout << 1+p << " " << x[p] << " " << y2 << "\n";
        }
        else cout << 1+p << " " << x2 << " " << y[p] << "\n";
        cout << 0 << " " << x2 << " " << y2 << "\n";return;
    }

}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifdef NCR
        init();
    #endif
    #ifdef SIEVE
        sieve();
    #endif
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3940kb

input:

1 2
1 1
5 3
6 2

output:

4
3
0 1 2
1 5 2
0 5 3

result:

ok correct

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3928kb

input:

2 1
1 1
6 1
1 3
6 3

output:

2
3
0 1 3
2 6 1
0 6 1

result:

wrong answer claimed 2.0000000000, actual 3.0000000000