QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#366060#7184. Transport PlusesGiga_Cronos#WA 0ms3896kbC++204.2kb2024-03-25 04:51:122024-03-25 04:51:13

Judging History

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

  • [2024-03-25 04:51:13]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3896kb
  • [2024-03-25 04:51:12]
  • 提交

answer

///Giga_Cronos Template from UH Top


#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops", "omit-frame-pointer", "inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma,tune=native")
#pragma GCC option("arch=native", "no-zero-upper") // Enable AVX
using namespace std;
///Macros
#define int long long
#define pb push_back
#define fs first
#define sc second
#define pf push_front
#define all(x) x.begin() , x.end()
#define rall(x) x.rbegin() , x.rend()
#define sz(x) (int)(x.size())
#define mid ((L+R)/2)

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector< pii > vpii;
typedef vector<vi> vvi;
typedef vector<vpii> vvpii;
typedef pair<vi,vi> pvv;
typedef __int128_t int128;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int ui;
///Constraints:
const int inf = ((1ll<<31ll)-1ll);
const long long INF = (((1ll<<60ll)-1ll)*2ll)+1ll;
const ull mod=998244353;
const ld pi = acos(-1);
const ld eps=1e-8;
/// Functions:
#define lg2(x) 31 - __builtin_clz(x)
#define lg2ll(x) 63ll - __builtin_clzll(x)
#define lgx(x,b) ( log(x) / log(b) )

/*#include<ext/pb_ds/assoc_container.hpp> // Common file
#include<ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
//comenta el define long long int
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// find_by_order
// order_of_key */
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

/// Quick Pow------------------------------------------------
int  qpow(int a, int b) {
int res = 1;
for (; b; b /= 2, a = (a*a)%mod) {
    if (b % 2) {
        res =(res*a)%mod;
    }
}
    return res;
}

int  qpow(int a, int b,int mod) {
int res = 1;
for (; b; b /= 2, a = (a*a)%mod) {
    if (b % 2) {
        res =(res*a)%mod;
    }
}
    return res;
}

///Inverso Modular
int InverM(int a,int b)
{
    int eso=a%b;
    if(eso==0)
        return 0;
    int ans=(1-(int128)b*InverM(b,eso))/eso;
    if(ans<0)
        ans+=b;
    return ans;
}
const int MAXN=200'005;
/// Variables-----------------------------------------------
int n,m,q,k;

ld Dist(pii A,pii B){
    B.fs-=A.fs;
    B.sc-=A.sc;
    return sqrt(B.fs*B.fs+B.sc*B.sc);
}

pii nearest(pii A,pii B){
    if(abs(A.fs-B.fs)<abs(A.sc-B.sc)){
        return {B.fs,A.sc};
    }else{
        return {A.fs,B.sc};
    }
}

void problem()
{
  int t;
  cin>>n>>t;
   vpii A(n+2);
   cin>>A[0].fs>>A[0].sc;
   cin>>A[n+1].fs>>A[n+1].sc;
   for(int i=1;i<=n;i++){
    cin>>A[i].fs>>A[i].sc;
   } 
   pair<ld,vector<pair<int,pii>>> Ans;
   Ans={Dist(A[0],A[n+1]),{{0,A[n+1]}} };
   int closer1=1;
   int closer2=1;
   for(int i=1;i<=n;i++){
       if(min(abs(A[0].fs-A[i].fs),abs(A[0].sc-A[i].sc))<min(abs(A[0].fs-A[closer1].fs),abs(A[0].sc-A[closer1].sc))){
        closer1=i;
       }
       if(min(abs(A[n+1].fs-A[i].fs),abs(A[n+1].sc-A[i].sc))<min(abs(A[n+1].fs-A[closer2].fs),abs(A[n+1].sc-A[closer2].sc))){
        closer2=i;
       } 
   } 
   Ans=min(Ans,{2*t+min(abs(A[0].fs-A[closer1].fs),abs(A[0].sc-A[closer1].sc))+min(abs(A[n+1].fs-A[closer2].fs),abs(A[n+1].sc-A[closer2].sc))
   , { {0,nearest(A[0],A[closer1])}
      ,{closer1,{A[closer1].fs,A[closer2].sc}}
      ,{closer2,nearest(A[n+1],A[closer2])}
      ,{0,A[n+1]}}   
    }); 
   for(int i=1;i<=n;i++){
       Ans=min(Ans,{t+min(abs(A[0].fs-A[i].fs),abs(A[0].sc-A[i].sc))+min(abs(A[n+1].fs-A[i].fs),abs(A[n+1].sc-A[i].sc)),
       {{0,nearest(A[0],A[i])}
        ,{i,nearest(A[n+1],A[i])}
        ,{0,A[n+1]}
       } 
       }
       ); 
   } 
    cout<<Ans.fs<<'\n';
   cout<<sz(Ans.sc)<<'\n';
   for(auto p:Ans.sc){
    cout<<p.fs<<' '<<p.sc.fs<<' '<<p.sc.sc<<'\n';
   }
   

}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed);
    cout.precision(12);
  //  freopen("a.in","r",stdin);
  //  freopen("a.out","w",stdout);

    int tc=1;
    //cin>>tc;
    while(tc--)
    {
        problem();
        cout<<'\n';
    }

}



///Tips
//Busqueda Binaria
//Precomputing
//Dinamic Programming
//Revisar constraints

詳細信息

Test #1:

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

input:

1 2
1 1
5 3
6 2

output:

4.000000000000
3
0 1 2
1 5 2
0 5 3


result:

ok correct

Test #2:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

2 1
1 1
6 1
1 3
6 3

output:

2.000000000000
4
0 1 1
1 1 3
2 6 1
0 6 1


result:

ok correct

Test #3:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

0 0
1 1
1 1

output:

0.000000000000
1
0 1 1


result:

ok correct

Test #4:

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

input:

0 0
100 100
0 0

output:

100.000000000000
4
0 100 0
1 0 0
1 0 0
0 0 0


result:

wrong answer Integer 1 violates the range [0, 0]