QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#799926#1449. Mountain Skylineucup-team1134#WA 1ms3868kbC++233.1kb2024-12-05 19:37:112024-12-05 19:37:12

Judging History

This is the latest submission verdict.

  • [2024-12-05 19:37:12]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3868kb
  • [2024-12-05 19:37:11]
  • 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<30;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";
    }
    
}

详细

Test #1:

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

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: 0ms
memory: 3716kb

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: 0ms
memory: 3596kb

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: 0ms
memory: 3868kb

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: 3868kb

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: -100
Wrong Answer
time: 0ms
memory: 3584kb

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
CC

result:

wrong output format Extra information in the output file