QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#564568 | #7184. Transport Pluses | kingmessi# | WA | 0ms | 3912kb | C++20 | 3.9kb | 2024-09-15 10:04:09 | 2024-09-15 10:04:10 |
Judging History
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){
p = cl.back();
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3912kb
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: 3796kb
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