QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#799918#1449. Mountain Skylineucup-team1134#TL 321ms3932kbC++233.1kb2024-12-05 19:35:242024-12-05 19:35:24

Judging History

This is the latest submission verdict.

  • [2024-12-05 19:35:24]
  • Judged
  • Verdict: TL
  • Time: 321ms
  • Memory: 3932kb
  • [2024-12-05 19:35:24]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=300005,INF=15<<26;

struct dat{
    ll x;
    ll y;
    ll z;
    string name;
};

const double eps=1e-9;

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;cin>>N;
    vector<dat> S(N);
    for(int i=0;i<N;i++){
        ll a,b,c;
        string d;cin>>a>>b>>c>>d;
        S[i]={a,b,c,d};
    }
    
    sort(all(S),[&](auto a,auto b){
        int at,bt;
        if(a.x==0){
            if(a.y>0) at=0;
            else at=2;
        }else if(a.x>0){
            at=1;
        }else{
            at=3;
        }
        
        if(b.x==0){
            if(b.y>0) bt=0;
            else bt=2;
        }else if(b.x>0){
            bt=1;
        }else{
            bt=3;
        }
        
        if(at!=bt){
            return at<bt;
        }
        
        if(at==0||at==2){
            if(a.z!=b.z) return a.z>b.z;
            else return abs(a.y)>abs(b.y);
        }else{
            ll re=a.x*b.y-a.y*b.x;
            if(re!=0){
                return re<0;
            }else{
                if(a.z!=b.z) return a.z>b.z;
                else return abs(a.x)>abs(b.x);
            }
        }
    });
    
    for(int i=0;i<N;i++){
        bool ok=true;
        for(int j=0;j<N;j++){
            if(i==j) continue;
            auto a=S[i],b=S[j];
            
            auto f=[&](double h){
                double res=hypot((double)a.x/a.z*h-b.x,(double)a.y/a.z*h-b.y)-(b.z-h);
                return res;
            };
            double l=0,r=min(a.z,b.z);
            for(int q=0;q<100;q++){
                double m1=(l+l+r)/3,m2=(l+r+r)/3;
                double f1=f(m1),f2=f(m2);
                if(f1<f2) r=m2;
                else l=m1;
                if(f1<=0||f2<=0){
                    ok=false;
                    break;
                }
            }
            
            //cout<<i<<" "<<j<<" "<<l<<" "<<f((l+r)/2)<<endl;
            if(f(l)>eps&&f(r)>eps&&f((l+r)/2)>eps){
                
            }else{
                ok=false;
                break;
            }
        }
        
        if(ok) cout<<S[i].name<<"\n";
    }
    
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3724kb

input:

3
0 10000 8849 EVEREST
10000 0 5959 LOGAN
0 -10000 4808 BLANC

output:

EVEREST
LOGAN
BLANC

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 3932kb

input:

6
8 0 5 FUJI
9 1 5 MATTERHORN
9 0 5 KEBNEKAISE
9 -1 5 FAGRADALSFJALL
16 0 10 KILIMANJARO
120 0 80 DENALI

output:

MATTERHORN
DENALI
FUJI
FAGRADALSFJALL

result:

ok 4 lines

Test #3:

score: 0
Accepted
time: 1ms
memory: 3724kb

input:

8
10 0 4 AX
0 10 4 AY
-10 0 3 CX
0 -10 3 CY
6 0 2 BX
-6 0 1 DX
0 6 2 BY
0 -6 1 DY

output:

AY
BY
AX
BX
CY
DY
CX
DX

result:

ok 8 lines

Test #4:

score: 0
Accepted
time: 1ms
memory: 3680kb

input:

4
0 -6 1 D
0 6 2 B
0 -10 3 C
0 10 4 A

output:

A
B
C
D

result:

ok 4 lines

Test #5:

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

input:

4
-6 0 1 D
6 0 2 B
-10 0 3 C
10 0 4 A

output:

A
B
C
D

result:

ok 4 lines

Test #6:

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

input:

13
9898 -1123 9898 AAA
4949 -2123 4949 BBB
4949 -6923 4949 CCC
2 1 2 A
2 2 2 B
2 3 2 C
2 4 2 D
2 5 2 E
-9897 1123 9897 AA
-9897 3123 9897 BB
-9897 9896 9897 CC
-9897 9897 9897 DD
-9897 9898 9897 EE

output:

A
AAA
AA

result:

ok 3 lines

Test #7:

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

input:

1
-6214 -7904 6286 BAA

output:

BAA

result:

ok single line: 'BAA'

Test #8:

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

input:

2
1096 3048 441 BAA
-8169 -9988 6030 BAB

output:

BAA
BAB

result:

ok 2 lines

Test #9:

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

input:

3
8686 -148 7301 BAA
7862 -6596 3113 BAB
-1427 -6616 3465 BAC

output:

BAA
BAC

result:

ok 2 lines

Test #10:

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

input:

4
5979 -8461 1456 BAA
1440 3585 3436 BAB
-8610 -7104 5215 BAC
-1156 -5771 1016 BAD

output:

BAB
BAA
BAD
BAC

result:

ok 4 lines

Test #11:

score: 0
Accepted
time: 1ms
memory: 3680kb

input:

10
-1870 -3207 978 BAA
-5687 8014 1784 BAB
5641 -2094 1664 BAC
-9329 -370 5729 BAD
-1887 -7780 963 BAE
-3798 -4239 1824 BAF
-3023 1307 470 BAG
5421 -3149 1104 BAH
9705 -625 378 BAI
8583 6506 6659 BAJ

output:

BAJ
BAI
BAC
BAH
BAE
BAA
BAF
BAD
BAG
BAB

result:

ok 10 lines

Test #12:

score: 0
Accepted
time: 6ms
memory: 3712kb

input:

50
-4890 -9660 3641 BAA
-15 7023 3366 BAB
-6231 321 4720 BAC
3729 -1491 2072 BAD
-8401 4916 942 BAE
-5336 -1429 3279 BAF
9563 -8527 4982 BAG
7742 -2885 5133 BAH
-9514 -9395 8192 BAI
1832 -9090 841 BAJ
6730 -6402 4802 BBA
-9950 -3694 5415 BBB
-1354 5291 4809 BBC
-8624 -1044 5060 BBD
5395 9638 4225 BB...

output:

BEC
BDB
BCF
BAH
BAD
BBJ
BBA
BEA
BBI
BAF
BAC
BED
BDF
BBC

result:

ok 14 lines

Test #13:

score: 0
Accepted
time: 48ms
memory: 3820kb

input:

200
5263 -9472 6719 BAA
6564 54 2675 BAB
4524 -8632 5835 BAC
9485 -8357 2619 BAD
-7800 -3613 2289 BAE
7804 6511 9011 BAF
1166 -3089 1714 BAG
5607 9945 8865 BAH
-8889 -109 260 BAI
1473 9107 8314 BAJ
6376 -2235 1390 BBA
5189 8269 8993 BBB
-2416 4304 4451 BBC
-2394 6744 4038 BBD
-7106 4475 4415 BBE
-18...

output:

CEH
BAJ
BJA
CJA
BCE
BFA
CJE
BHD
CFG
BAA
BAC
CHE
CEG
CAJ
CAB
CCE
BDG
BEE
BHH
CIA
CCH
CAD
BBC
BCF

result:

ok 24 lines

Test #14:

score: 0
Accepted
time: 321ms
memory: 3696kb

input:

500
-2000 -4403 3457 BAA
-8075 -8578 619 BAB
8485 -6656 1821 BAC
9641 -746 1064 BAD
-8573 248 2687 BAE
-8080 6673 6056 BAF
-1092 -7768 657 BAG
1244 9849 123 BAH
7702 -8473 2851 BAI
8455 6566 5978 BAJ
2866 -6101 820 BBA
5346 -2382 233 BBB
2943 2886 2770 BBC
-5188 4666 5249 BBD
-9026 1123 1740 BBE
287...

output:

ECH
FBA
BDB
DFC
FJC
FEI
FBJ
BDH
CBC
CJA
DGD
EJH
CAD
CID
BID
EFA
BBF
CAE
BGH
BJA
DJD
DBD
FIJ
BAA
CDJ
EFI
FCE
DHC
FAA
FHB
FAI
CDI
CBD
CGF
BEH
CHJ
EDH
BCI
EJE

result:

ok 39 lines

Test #15:

score: -100
Time Limit Exceeded

input:

999
9128 -2481 6086 BAA
-2871 6747 5922 BAB
-5883 6608 5302 BAC
-2099 -6075 1525 BAD
3486 9110 4312 BAE
-4395 9007 6773 BAF
-7484 8891 5021 BAG
-5288 -9473 4190 BAH
-7997 -3467 6779 BAI
221 -5599 1063 BAJ
1846 -9335 2286 BBA
809 -3879 1050 BBB
8878 -9975 8177 BBC
-7179 2532 6400 BBD
-4865 6388 5563 ...

output:


result: