QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#799926 | #1449. Mountain Skyline | ucup-team1134# | WA | 1ms | 3868kb | C++23 | 3.1kb | 2024-12-05 19:37:11 | 2024-12-05 19:37:12 |
Judging History
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