QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#547607 | #4371. Spin Doctor | PhantomThreshold | WA | 387ms | 51724kb | C++17 | 6.5kb | 2024-09-04 23:51:32 | 2024-09-04 23:51:32 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long db;
typedef long long ll;
const db eps=0;
const db INF=1e10;
int sign(db k){
if (k>eps) return 1;
else if (k<-eps) return -1;
return 0;
}
int cmp(db k1,db k2){return sign(k1-k2);}
int inmid(db k1,db k2,db k3){return sign(k1-k3)*sign(k2-k3)<=0;}
struct point{
db x,y;
point operator + (const point &k1) const{return (point){x+k1.x,y+k1.y};}
point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
point operator * (db k1) const{return (point){x*k1,y*k1};}
db abs2(){
return x*x+y*y;
}
db dis2(point k1){
return ((*this)-k1).abs2();
}
bool operator < (const point &k1) const{
int fl=cmp(x,k1.x);
if (fl==-1) return true;
if (fl==1) return false;
return cmp(y,k1.y)==-1;
}
bool operator == (const point &k1) const{
return cmp(x,k1.x)==0 && cmp(y,k1.y)==0;
}
bool operator > (const point &k1) const{
int fl=cmp(x,k1.x);
if (fl==1) return true;
if (fl==-1) return false;
return cmp(y,k1.y)==1;
}
int getP(){
return sign(y)==-1 || (sign(y)==0 && sign(x)==-1);
}
friend ostream& operator << (ostream &os,const point &k){
os << "(" << k.x << "," << k.y << ")";
return os;
}
};
int inmid(point k1,point k2,point k3){
return inmid(k1.x,k2.x,k3.x) && inmid(k1.y,k2.y,k3.y);
}
db cross(point k1,point k2){
return k1.x*k2.y-k1.y*k2.x;
}
db dot(point k1,point k2){
return k1.x*k2.x+k1.y*k2.y;
}
vector<point> ConvexHull(vector<point> A,int flag=1){
int n=A.size();
vector<point>ans(n*2);
sort(A.begin(),A.end());
int now=-1;
for (int i=0;i<(int)A.size();i++){
while (now>0 && sign(cross(ans[now]-ans[now-1],A[i]-ans[now-1]))<flag) now--;
ans[++now]=A[i];
}
int pre=now;
for (int i=n-2;i>=0;i--){
while (now>pre && sign(cross(ans[now]-ans[now-1],A[i]-ans[now-1]))<flag) now--;
ans[++now]=A[i];
}
ans.resize(now);
return ans;
}
struct Convex{
int n;
vector<point> a,upper,lower;
Convex(vector<point> _a):a(_a){
n=a.size();
int ptr=0;
for (int i=1;i<n;i++) if (a[ptr]<a[i]) ptr=i;
for (int i=0;i<=ptr;i++) lower.push_back(a[i]);
for (int i=ptr;i<n;i++) upper.push_back(a[i]);
upper.push_back(a[0]);
}
int sign(long long x){
return x<0?-1:x>0;
}
void update_tangent(const point &p,int id,int &i0,int &i1){
if (cross(a[i0]-p,a[id]-p)>0) i0=id;
if (cross(a[i1]-p,a[id]-p)<0) i1=id;
}
void binary_search(int l,int r,point p,int &i0,int &i1){
if (l==r) return;
update_tangent(p,l%n,i0,i1);
int sl=sign(cross(a[l%n]-p,a[(l+1)%n]-p));
for (;l+1<r;){
int mid=(l+r)/2;
int smid=sign(cross(a[mid%n]-p,a[(mid+1)%n]-p));
if (smid==sl) l=mid;
else r=mid;
}
update_tangent(p,r%n,i0,i1);
}
bool contain(point p){
if (p.x<lower[0].x || p.x>lower.back().x) return false;
int id=lower_bound(lower.begin(),lower.end(),(point){p.x,-INF})-lower.begin();
if (lower[id].x==p.x){
if (lower[id].y>p.y) return false;
}
else if (cross(lower[id-1]-p,lower[id]-p)<0)
return false;
id=lower_bound(upper.begin(),upper.end(),(point){p.x,INF},greater<point>())-upper.begin();
if (upper[id].x==p.x){
if (upper[id].y<p.y) return false;
}
else if (cross(upper[id-1]-p,upper[id]-p)<0) return false;
return true;
}
bool get_tangent(point p,int &i0,int &i1){
if (contain(p)) return false;
i0=i1=0;
int id=lower_bound(lower.begin(),lower.end(),p)-lower.begin();
binary_search(0,id,p,i0,i1);
binary_search(id,(int)lower.size(),p,i0,i1);
id=lower_bound(upper.begin(),upper.end(),p,greater<point>())-upper.begin();
binary_search((int)lower.size()-1,(int)lower.size()-1+id,p,i0,i1);
binary_search((int)lower.size()-1+id,(int)lower.size()-1+(int)upper.size(),p,i0,i1);
return true;
}
};
int main(){
int n;
cin >> n;
vector<point> wp;
vector<point> bp;
db cntw=0,cntb=0;
for (int i=1;i<=n;i++){
db x,y;
int col;
cin >> x >> y >> col;
if (col==0){
cntw++;
wp.emplace_back((point){x,y});
}
else{
cntb++;
bp.emplace_back((point){x,y});
}
}
if (cntb==1){
cout << 1 << "\n";
return 0;
}
db ans=cntb;
sort(bp.begin(),bp.end());
bp.resize(unique(bp.begin(),bp.end())-bp.begin());
vector<point> CHB=bp;
if (bp.size()>=3) CHB=ConvexHull(bp);
if (CHB.size()<=2){
point st=CHB.front();
point ed=CHB.back();
for (auto P:wp) if (inmid(st,ed,P) && sign(cross(P-st,ed-st))==0) ans++;
cout << ans << "\n";
return 0;
}
// cerr << "---------------------" << endl;
// cerr << "Convex Hull of black : " << endl;
// for (auto e:CHB) cerr << e << endl;
// cerr << "---------------------" << endl;
ll base=0;
Convex conv(CHB);
vector<point> dir;
vector<pair<point,ll>> vup;
for (auto P:wp){
int st=0,ed=0;
bool flag=conv.get_tangent(P,st,ed);
if (!flag){
ans++;
continue;
}
point dirst=CHB[st]-P;
point dired=CHB[ed]-P;
if (sign(cross(dirst,dired))<0) swap(dirst,dired);
if (dirst.getP()) dirst=dirst*(-1);
if (dired.getP()) dired=dired*(-1);
dir.emplace_back(dirst);
dir.emplace_back(dired);
vup.emplace_back(dirst,1LL);
vup.emplace_back(dired,-1LL);
if (sign(cross(dirst,dired))<0) base++;
}
dir.emplace_back((point){1,0});
sort(dir.begin(),dir.end(),
[&](const point &X,const point &Y){
return sign(cross(X,Y))>0;
}
);
dir.resize(
unique(dir.begin(),dir.end(),
[&](const point &X,const point &Y){
return sign(cross(X,Y))==0;
}
)
-dir.begin()
);
dir.emplace_back((point){-1,0});
{
vector<point> tmp;
int sz=dir.size();
for (int i=0;i<=sz-2;i++){
tmp.emplace_back(dir[i]);
tmp.emplace_back(dir[i]+dir[i+1]);
}
swap(dir,tmp);
}
// cerr << "ans : " << ans << endl;
// for (auto d:dir){
// cerr << "dir : " << d << endl;
// }
auto cmp = [&](const pair<point,ll> &X,const pair<point,ll> &Y){
int flag=sign(cross(X.first,Y.first));
if (flag!=0) return flag==1;
return X.second>Y.second;
};
sort(vup.begin(),vup.end(),cmp);
vector<ll> sumup(vup.size()+1);
if (vup.size()) sumup[0]=vup[0].second;
for (int i=1;i<(int)vup.size();i++) sumup[i]=sumup[i-1]+vup[i].second;
// for (auto [vec,val]:dir){
// cerr << "vec,val : " << vec << " " << val << endl;
// }
ll mn=1e9;
for (auto d:dir){
int pos=upper_bound(vup.begin(),vup.end(),make_pair(d,0LL),cmp)-vup.begin()-1;
mn=min(mn,base+sumup[pos]);
}
ans+=mn;
cout << ans << "\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3656kb
input:
6 0 10 0 10 0 1 12 8 1 5 5 0 11 2 1 11 3 0
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
10 6 1 1 0 2 0 2 1 1 6 1 1 8 2 0 4 4 0 4 0 0 2 3 1 6 1 0 6 3 1
output:
8
result:
ok single line: '8'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
5 5 7 0 3 4 0 5 7 0 5 7 1 9 4 0
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
100 7487 4751 1 7499 5064 1 7471 5376 1 7404 5683 1 7300 5979 1 7159 6260 1 6984 6520 1 6777 6757 1 6543 6966 1 6284 7144 1 6006 7288 1 5711 7396 1 5405 7466 1 5092 7498 1 4780 7490 1 4469 7442 1 4167 7357 1 3878 7234 1 3607 7075 1 3358 6884 1 3135 6664 1 2941 6417 1 2780 6147 1 2653 5860 1 2564 555...
output:
61
result:
ok single line: '61'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
200 7489 1285 0 6851 8471 0 6122 2766 1 2413 9338 0 1725 7382 0 6984 6520 1 5080 8417 0 2604 5711 1 5833 2643 1 48 2810 0 5316 2439 0 900 7419 0 6809 867 0 6006 7288 1 5092 7498 1 5531 2558 1 7075 6393 1 9979 9313 0 7436 4441 1 4595 2534 1 2598 909 0 842 284 0 3358 6884 1 6522 7976 0 604 5833 0 3607...
output:
125
result:
ok single line: '125'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
300 2253 823 1 1865 9556 0 306 6720 1 8588 1519 1 2756 9468 1 5810 9933 1 1625 9138 0 27 932 0 8124 1097 1 8699 8363 1 7202 9489 1 9420 7337 1 9862 6164 1 908 2128 1 9341 2521 1 372 8140 0 9318 7520 1 1760 34 0 785 612 0 1445 1442 0 9694 3280 1 9496 2152 0 9249 1891 0 2162 9828 0 580 2663 1 1269 832...
output:
234
result:
ok single line: '234'
Test #7:
score: 0
Accepted
time: 81ms
memory: 16480kb
input:
100000 7487 4751 1 7487 4751 1 7487 4752 1 7487 4752 1 7487 4752 1 7487 4752 1 7487 4753 1 7487 4753 1 7487 4753 1 7487 4754 1 7487 4754 1 7487 4754 1 7487 4755 1 7487 4755 1 7487 4755 1 7487 4756 1 7488 4756 1 7488 4756 1 7488 4757 1 7488 4757 1 7488 4757 1 7488 4757 1 7488 4758 1 7488 4758 1 7488 ...
output:
68833
result:
ok single line: '68833'
Test #8:
score: 0
Accepted
time: 88ms
memory: 16868kb
input:
100000 8980 4601 1 8980 4602 1 8980 4602 1 8980 4603 1 8980 4603 1 8980 4604 1 8980 4604 1 8980 4605 1 8980 4605 1 8980 4606 1 8980 4606 1 8980 4607 1 8980 4607 1 8980 4608 1 8980 4608 1 8980 4609 1 8980 4609 1 8980 4610 1 8980 4610 1 8980 4611 1 8981 4611 1 8981 4612 1 8981 4612 1 8981 4613 1 8981 ...
output:
79761
result:
ok single line: '79761'
Test #9:
score: 0
Accepted
time: 94ms
memory: 16536kb
input:
100000 9975 4501 1 9975 4502 1 9975 4503 1 9975 4503 1 9975 4504 1 9975 4504 1 9975 4505 1 9975 4506 1 9975 4506 1 9975 4507 1 9975 4508 1 9975 4508 1 9975 4509 1 9975 4509 1 9975 4510 1 9975 4511 1 9976 4511 1 9976 4512 1 9976 4513 1 9976 4513 1 9976 4514 1 9976 4514 1 9976 4515 1 9976 4516 1 9976 ...
output:
79877
result:
ok single line: '79877'
Test #10:
score: 0
Accepted
time: 88ms
memory: 18264kb
input:
100000 89749 223387 0 295171 424382 0 397151 279092 1 393939 207794 1 109069 198636 1 338201 128673 1 388987 306412 1 401174 201459 0 428943 426416 0 292775 106229 1 181076 383227 1 207577 106125 1 389057 405639 0 358258 146173 1 376103 425370 0 284279 396030 1 342155 368352 1 479748 52614 0 102762 ...
output:
72070
result:
ok single line: '72070'
Test #11:
score: 0
Accepted
time: 95ms
memory: 16472kb
input:
100000 649 24758 0 14496 41252 0 39286 10853 0 19975 37285 1 40085 29490 0 1766 27831 0 5842 586 0 27105 8225 1 11312 32491 1 17523 4856 0 16990 8550 1 4916 12992 0 7696 24913 1 42700 5177 0 43755 27268 0 9922 42370 0 8555 16976 1 17794 36896 0 21532 37468 1 35271 30549 0 31468 10477 1 37030 18776 1...
output:
74280
result:
ok single line: '74280'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
3 100 100 1 500 500 1 200 200 0
output:
3
result:
ok single line: '3'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
5 0 100 0 0 200 1 0 300 0 0 400 1 0 500 0
output:
3
result:
ok single line: '3'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
7 100 0 0 200 0 1 300 0 0 400 0 1 500 0 0 600 0 1 700 0 0
output:
5
result:
ok single line: '5'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
5 0 0 1 100 100 1 50 50 0 50 25 0 25 50 0
output:
3
result:
ok single line: '3'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
1 0 0 1
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
2 0 0 1 0 0 0
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
2 0 0 1 0 1 0
output:
1
result:
ok single line: '1'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
5 100 100 1 50 50 0 100 200 0 150 150 0 100 100 0
output:
1
result:
ok single line: '1'
Test #20:
score: 0
Accepted
time: 129ms
memory: 9452kb
input:
250000 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964018 389997 0 1964...
output:
250000
result:
ok single line: '250000'
Test #21:
score: 0
Accepted
time: 224ms
memory: 32468kb
input:
250000 8550 5546 1 1572 3657 1 7112 3904 1 4958 6472 1 6621 8971 1 7230 7901 1 1460 4459 1 3076 5535 1 2823 3202 1 4314 6444 1 5323 9275 1 976 6014 1 9105 7435 1 6937 5228 1 6610 5712 1 8099 5810 1 7207 2629 1 9527 3777 1 3790 3671 1 3223 9511 1 922 2799 1 2708 4697 1 5454 9118 1 7530 9036 1 885 429...
output:
203548
result:
ok single line: '203548'
Test #22:
score: 0
Accepted
time: 129ms
memory: 25108kb
input:
100000 6586 9605 1 688 2874 1 8700 7949 1 4623 47 1 378 3451 1 5368 46 1 309 6390 1 9344 2926 1 8645 8012 1 9105 7435 1 6101 204 1 26 5094 1 41 5318 1 3223 9511 1 9691 6390 1 7664 8934 1 7007 9384 1 1637 8315 1 7530 9036 1 119 4206 1 8082 1418 1 4053 158 1 7263 9224 1 6658 429 1 1883 8550 1 5094 997...
output:
63494
result:
ok single line: '63494'
Test #23:
score: 0
Accepted
time: 130ms
memory: 25232kb
input:
100000 42796 30581 1 27459 44131 1 42756 14344 1 44098 17439 1 18059 44290 1 3096 32112 1 29881 1849 1 42046 13114 1 1641 29437 1 12475 41636 1 10539 4777 1 1458 29023 1 25506 359 1 41181 11813 1 17727 810 1 24795 44765 1 31345 2629 1 14436 2195 1 33256 41132 1 2325 30806 1 4517 34129 1 42771 30628 ...
output:
64584
result:
ok single line: '64584'
Test #24:
score: 0
Accepted
time: 387ms
memory: 51724kb
input:
250000 179223 507524 1 1953878 749817 1 1074428 1995760 1 1038476 1261 1 1873442 1414315 1 1997919 1050970 1 1994767 916993 1 1441559 143861 1 1873064 1414930 1 1021459 1999488 1 1999780 991906 1 46502 748785 1 134097 573595 1 1761948 1566969 1 564999 1860407 1 258192 1590279 1 1305866 68863 1 10008...
output:
177485
result:
ok single line: '177485'
Test #25:
score: 0
Accepted
time: 39ms
memory: 5312kb
input:
100000 25413 13041 0 3240 31742 0 40224 14017 0 9635 20131 0 9251 7361 0 24737 13064 0 13794 13768 0 10113 17490 0 13701 38317 0 30220 25996 0 16214 26720 0 18824 6185 0 18437 41476 0 10938 29854 0 37321 19798 0 41255 20820 0 15690 11981 0 7363 14764 0 13435 43392 0 35370 27782 0 37816 15984 0 20974...
output:
1996
result:
ok single line: '1996'
Test #26:
score: 0
Accepted
time: 78ms
memory: 17292kb
input:
100000 42808 16570 0 13470 16294 0 21837 20456 0 27633 44832 1 43204 31337 0 30846 42318 1 5023 279 0 22500 26620 0 25367 7969 0 25659 16149 1 17340 13731 0 38255 24494 1 13912 3828 0 41341 38404 0 5992 15677 0 18686 26358 0 13515 1119 0 33085 856 0 24749 42396 0 42354 36978 1 10881 39037 0 59 20782...
output:
51005
result:
ok single line: '51005'
Test #27:
score: 0
Accepted
time: 82ms
memory: 17820kb
input:
100000 1295 9516 0 44028 7323 0 22333 23362 0 29472 11339 0 43478 3715 0 31422 11315 0 22500 4988 1 22500 26016 1 6290 12990 0 25921 13160 0 17287 2499 0 30987 13164 0 16024 14510 0 36614 1377 0 11390 42489 1 4761 31273 0 26159 5541 0 38317 1908 0 19293 43226 0 40557 33871 0 16510 19308 1 29122 4453...
output:
51027
result:
ok single line: '51027'
Test #28:
score: 0
Accepted
time: 75ms
memory: 17124kb
input:
100000 24808 42282 0 21168 34391 0 6444 786 0 39361 18331 0 15246 38500 0 22271 34860 0 3431 2169 0 37636 43046 0 18143 19155 0 43898 19065 0 26106 36485 0 11957 25354 0 41529 17038 0 4395 40101 0 5213 13660 0 21949 6678 0 13011 4705 0 39046 20188 0 34676 7351 0 29493 231 0 25178 23889 0 15680 7594 ...
output:
51056
result:
ok single line: '51056'
Test #29:
score: 0
Accepted
time: 42ms
memory: 5432kb
input:
100000 35178 7556 0 43543 24751 0 5084 35731 0 16305 36844 0 22500 20264 0 1630 8212 0 11095 211 0 42801 6599 0 37701 2028 0 17070 1280 0 507 42420 0 14316 5603 0 32825 40550 0 32020 4685 0 22500 6619 1 7743 20810 0 32411 1420 0 42622 23150 0 18429 77 0 8623 17599 0 26346 28983 0 6475 19645 0 30712 ...
output:
1982
result:
ok single line: '1982'
Test #30:
score: 0
Accepted
time: 76ms
memory: 17632kb
input:
100000 44615 16896 0 35703 38357 0 4266 10295 1 3924 27703 0 43769 21876 0 376 32019 0 26638 37892 0 1486 43624 0 42332 30447 0 21852 6617 1 20000 23382 0 32297 4803 1 14563 34582 0 7667 22386 0 26562 23139 0 25281 7017 1 24027 29563 0 21471 43979 0 6113 36704 0 10743 28455 0 20694 10227 0 16574 402...
output:
50748
result:
ok single line: '50748'
Test #31:
score: 0
Accepted
time: 214ms
memory: 18144kb
input:
249943 52338 1932288 0 500604 85230 1 421975 541172 0 1220260 1922275 0 782273 1935347 0 1100991 1806280 0 205837 836278 0 314341 849646 0 482026 1814471 0 1006377 1795879 0 457197 1895481 1 612248 1804355 0 831860 7724 1 1975517 1191035 0 1838023 357991 0 1884236 960643 0 1978434 1272346 1 830 1056...
output:
237745
result:
ok single line: '237745'
Test #32:
score: -100
Wrong Answer
time: 168ms
memory: 11952kb
input:
249924 1692009 1277080 0 1701311 1473926 0 1530920 1558948 0 809839 1544501 0 490718 1778464 0 1596606 1610103 0 1048061 322345 0 1093714 303163 0 1230443 1349196 0 85588 499676 1 710370 217252 0 700457 890768 0 1040631 611336 0 1222799 946458 0 1910466 490490 1 1683127 754616 0 876618 906063 0 4071...
output:
249957
result:
wrong answer 1st lines differ - expected: '249924', found: '249957'