QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#799918 | #1449. Mountain Skyline | ucup-team1134# | TL | 321ms | 3932kb | C++23 | 3.1kb | 2024-12-05 19:35:24 | 2024-12-05 19:35:24 |
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<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";
}
}
詳細信息
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 ...