QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#799925 | #1449. Mountain Skyline | ucup-team1134# | TL | 578ms | 3936kb | C++23 | 3.1kb | 2024-12-05 19:36:22 | 2024-12-05 19:36:28 |
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<40;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: 3728kb
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: 3840kb
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: 3928kb
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: 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: 3872kb
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: 1ms
memory: 3852kb
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: 3560kb
input:
1 -6214 -7904 6286 BAA
output:
BAA
result:
ok single line: 'BAA'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3708kb
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: 3928kb
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: 3932kb
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: 3864kb
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: 3ms
memory: 3708kb
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: 22ms
memory: 3740kb
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: 133ms
memory: 3892kb
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: 0
Accepted
time: 578ms
memory: 3728kb
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:
GBA BAAB JHC BAIH ECD CJD HDJ BDH EHF IEF IEB BCG DAE BHC BJI GGJ DBJ BADJ BEF CAE DHD GHB ECE BAHG GJI IGA BAFG JJC IIF IJC EIB GCJ EGI CEE HGI JIG IHE JGF CEG CAG FIE EDD BADD BAHI IEE HCF FDB GBH BEE JJF DGH GIB BAHE EGD GGE JCH FIG EDJ EAH DHE EHH HAE HGD BAEJ BFJ
result:
ok 65 lines
Test #16:
score: 0
Accepted
time: 458ms
memory: 3732kb
input:
1000 2840 -1095 2563 BAA -2608 4560 4755 BAB -4019 -3659 3894 BAC 931 9419 5728 BAD -9923 -9959 9831 BAE 2146 -8981 1359 BAF -1456 309 1135 BAG -6016 8207 1692 BAH 8838 -60 7521 BAI 3037 -1111 2580 BAJ -73 8449 5735 BBA -683 6019 6050 BBB -9853 2512 3203 BBC -6502 -5807 6239 BBD 6811 8376 419 BBE -7...
output:
BIE IIG DFA EGI DIC DDE BADG HDD IDF DEA GEH IDA DHH FFC EBB BEH JAD BJE CHG GJD IGJ CID FHH BCA IIA BAGB JBB CCF CDJ HFE GIE DBB DDJ ECE JII DDI FHI CEF BBB HFC
result:
ok 40 lines
Test #17:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
1 5050 -4552 3409 BAA
output:
BAA
result:
ok single line: 'BAA'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
2 -5100 -7748 4632 BAA 760 -7202 3623 BAB
output:
BAB BAA
result:
ok 2 lines
Test #19:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
3 9932 3940 5348 BAA -8637 -9285 6341 BAB 5737 -2768 3175 BAC
output:
BAA BAC BAB
result:
ok 3 lines
Test #20:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
4 7225 8186 5454 BAA -5475 8632 5108 BAB -684 -28 333 BAC -3174 2761 2107 BAD
output:
BAA BAC BAD BAB
result:
ok 4 lines
Test #21:
score: 0
Accepted
time: 1ms
memory: 3936kb
input:
10 -624 -3704 1868 BAA 3242 3358 2342 BAB 3516 -5708 3360 BAC -3893 2054 2210 BAD -3007 8912 4702 BAE -4486 -7791 4490 BAF -9065 8912 6360 BAG 2268 -6141 3271 BAH -9542 192 4771 BAI -4146 -9735 5289 BAJ
output:
BAB BAC BAH BAA BAJ BAF BAI BAD BAG BAE
result:
ok 10 lines
Test #22:
score: 0
Accepted
time: 4ms
memory: 3620kb
input:
50 8893 -1969 4544 BAA -8520 5685 5123 BAB 5302 -4032 3320 BAC 8908 2744 4652 BAD 2556 -2237 1690 BAE 2321 -6087 3250 BAF 7986 6113 5035 BAG 5426 5564 3893 BAH -9188 -2365 4739 BAI -4162 1671 2236 BAJ -563 5865 2943 BBA 2660 3676 2266 BBB -900 -5488 2777 BBC -4558 -7210 4269 BBD -3282 1769 1869 BBE ...
output:
BDG BDB BCE BBB BAH BBF BAG BDE BCH BEA BAD BBJ BDF BAA BDA BBH BCF BAC BAE BDH BCJ BEJ BDC BAF BCC BCD BDD BEC BBC BDJ BBD BCG BBI BDI BBG BCB BEI BEB BAI BEF BAJ BCI BBE BAB BED BCA BEE BEG BEH BBA
result:
ok 50 lines
Test #23:
score: 0
Accepted
time: 52ms
memory: 3728kb
input:
200 6509 -9970 5960 BAA 8650 826 4339 BAB -8119 6144 5094 BAC 7105 -6209 4716 BAD 7612 4244 4366 BAE 8796 -2206 4543 BAF -3544 3991 2673 BAG 1630 7159 3676 BAH 1025 -9216 4636 BAI 2340 11 1174 BAJ -443 -8921 4465 BBA 7739 3969 4340 BBB -1414 1302 970 BBC 3818 -626 1931 BBD 1001 4349 2224 BBE 1914 50...
output:
CFJ BBJ CJD BJD BDC CIH BAH BBE BEE BBG BDB BEF CEF BEG BBF BGB CDF BHJ BFA CIC CBA BIJ CGD CCD CHD BFI BGG BFC BDJ BEB BDE BAE BBB BDG BDA CCJ CJB CAE BFE CGF BBH CIG BFB BAB CHF BAJ CAC CEB BGE BBD BAF BGF BFG CBF CAD CJJ CED CBE BJH BHA BHE CAI BFJ BJG CIB CBI BAD BCB CCB CGH CGE BCE BIF BHB CGC ...
result:
ok 196 lines
Test #24:
score: 0
Accepted
time: 314ms
memory: 3832kb
input:
500 -754 4803 2438 BAA 9842 1260 4957 BAB -5614 7810 4799 BAC -8650 932 4343 BAD 7364 7775 5346 BAE -3459 -8842 4746 BAF 6455 6858 4712 BAG -6482 -1748 3362 BAH -679 3589 1832 BAI -4768 -7874 4593 BAJ -6385 7985 5101 BBA 9402 2507 4859 BBB 8530 -3672 4640 BBC 3510 4332 2791 BBD -5304 7156 4446 BBE -...
output:
CJF BII EJC EEH EDF EEA CBB CFG FFH BFJ DIF EHA FCE CBF CCD EJD BIF FJF DIA FED FEJ BJI FCA CAH DAD DIE EEI BDB BIG CBH EAI DCE EAB EIH EJE EGA BHE DGE FBE DCD BEB BCH DCH BCI BGE EFD BBD FIG DJF FII BEH FCG FAE BAG BAE CDI DDH EJF CAG EHC BBH CCJ FCI FHJ DGB EGB EJB BFA FGA BGI FBJ CJD FBD FIC BDD ...
result:
ok 472 lines
Test #25:
score: -100
Time Limit Exceeded
input:
999 -9627 6725 5864 BAA 8319 9533 6329 BAB -406 -1944 1001 BAC 6995 9031 5717 BAD -3219 -4202 2642 BAE 4069 -356 2050 BAF 189 -4833 2421 BAG 2514 -9243 4790 BAH -2634 6981 3728 BAI -5639 -349 2820 BAJ -1273 -2111 1224 BBA 3416 3024 2275 BBB -3433 -1454 1863 BBC 152 6203 3094 BBD -9092 -2453 4700 BBE...