QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #373113 | #4371. Spin Doctor | InfinityNS | Compile Error | / | / | C++14 | 4.3kb | 2024-04-01 02:40:30 | 2024-04-01 02:40:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
struct pt{
ll x,y;
pt():x(0),y(0){}
pt(ll a,ll b):x(a),y(b){}
};
pt operator - (pt a,pt b){return pt(a.x-b.x,a.y-b.y);}
ll cross(pt a,pt b){return a.x*b.y-a.y*b.x;}
ll dot(pt a,pt b){return a.x*b.x+a.y*b.y;}
int part(pt a){return a.y<0 || (a.y==0 && a.x<0);}
bool operator < (pt a,pt b){return mp(part(a),(ll)0)<mp(part(b),cross(a,b));}
bool operator == (pt a,pt b){return mp(a.x,a.y)==mp(b.x,b.y);}
int sgn(ll x){return x==0?0:(x<0?-1:1);}
const int N=250050;
pt pts[N];
int c[N];
bool cmp(pt a,pt b){return mp(a.x,a.y)<mp(b.x,b.y);}
vector<pt> ConvexHull(vector<pt> poly){
sort(poly.begin(),poly.end(),cmp);
poly.erase(unique(poly.begin(),poly.end()),poly.end());
if(poly.size()<2)return poly;
vector<pt> hull;
int sz=0;
for(int t=0;t<2;t++){
int was=sz;
for(auto p:poly){
while(sz>was+1 && cross(hull[sz-1]-hull[sz-2],p-hull[sz-2])<=0){
hull.pop_back();
sz--;
}
hull.pb(p);
sz++;
}
hull.pop_back();
sz--;
reverse(poly.begin(),poly.end());
}
return hull;
}
bool OnSeg(pt a,pt b,pt p){
pt v=b-a;
if(cross(v,p-a)!=0)return false;
ll da=dot(v,a);
ll dp=dot(v,p);
ll db=dot(v,b);
return da<=dp && dp<=db;
}
bool InTriangle(pt a,pt b,pt c,pt p){
vector<pt> poly={a,b,c};
bool lo=false,hi=false;
for(int i=0;i<3;i++){
ll cr=cross(poly[i]-p,poly[(i+1)%3]-p);
if(cr<0)lo=true;
if(cr>0)hi=true;
}
return !lo || !hi;
}
bool Inside(vector<pt>& poly, pt p){
if(poly.size()==1)return p==poly[0];
if(poly.size()==2)return OnSeg(poly[0],poly[1],p);
int bot=0,top=(int)poly.size()-3,ans=0;
while(bot<=top){
int mid=top+bot>>1;
if(cross(poly[mid]-poly.back(),p-poly.back())>=0){
bot=mid+1;
ans=mid;
}else{
top=mid-1;
}
}
//printf("Inside? %i\n",ans);
return InTriangle(poly[ans],poly[ans+1],poly.back(),p);
}
pt Solve(vector<pt>& poly,pt p,int l,int r,int sg){
int bot=l,top=r-1,ans=r;
while(bot<=top){
int mid=bot+top>>1;
if(sgn(cross(poly[mid]-p,poly[mid+1]-p))==sg){
bot=mid+1;
ans=mid;
}else{
top=mid-1;
}
}
//printf("Solve (%lld, %lld) l:%i r:%i -- %i (%lld, %lld)\n",p.x,p.y,l,r,ans,poly[ans].x,poly[ans].y);
return poly[ans]-p;
}
pair<pt,pt> Tangents(vector<pt>& poly, pt p){
if(poly.size()==1)return {poly[0]-p,poly[0]-p};
if(poly.size()==2){
if(cross(poly[0]-p,poly[1]-p)>=0)return {poly[0]-p,poly[1]-p};
else return {poly[1]-p,poly[0]-p};
}
int bot=1,top=(int)poly.size()-2,ans=0;
int s1=sgn(cross(poly.back()-p,poly.front()-p));
while(top>=bot){
int mid=top+bot>>1;
if(sgn(cross(poly.back()-p,poly[mid]-p))==s1){
ans=mid;
bot=mid+1;
}else{
top=mid-1;
}
}
//printf("Split\n");
//for(int i=0;i<=ans;i++)printf("(%lld, %lld) ",poly[i].x,poly[i].y);printf("\n");
//for(int i=ans+1;i<poly.size();i++)printf("(%lld, %lld) ",poly[i].x,poly[i].y);printf("\n");
if(s1==0)s1=-sgn(cross(poly.back()-p,poly[ans+1]-p));
pt L=Solve(poly,p,0,ans,-s1);
pt R=Solve(poly,p,ans+1,(int)poly.size()-1,s1);
if(s1==-1)swap(L,R);
return {L,R};
}
int main(){
int n;
scanf("%i",&n);
vector<pt> poly;
for(int i=1;i<=n;i++){
scanf("%lld %lld %i",&pts[i].x,&pts[i].y,&c[i]);
if(c[i]==1)poly.pb(pts[i]);
}
if(poly.size()==1){
printf("1\n");
return 0;
}
poly=ConvexHull(poly);
//printf("Convex hull: ");
//for(pt p:poly)printf("(%lld, %lld) ",p.x,p.y);
//printf("\n");
ll mny=poly[0].y,mxy=poly[0].y;
for(int i=1;i<poly.size();i++){
mny=min(mny,poly[i].y);
mxy=max(mxy,poly[i].y);
}
int cnt=0;
vector<pt> cand;
for(int i=1;i<=n;i++){
if(Inside(poly,pts[i])){
//printf("%i(%lld, %lld) is inside\n",i,pts[i].x,pts[i].y);
cnt++;
}else{
cand.pb(pts[i]);
}
}
vector<pair<pt,int>> evs;
for(int i=0;i<cand.size();i++){
//printf("Cand (%lld, %lld)\n",cand[i].x,cand[i].y);
pt L,R;
tie(L,R)=Tangents(poly,cand[i]);
if(part(L))L=-L;
if(part(R))R=-R;
//printf("Tangents L(%lld, %lld) R(%lld, %lld)\n",L.x,L.y,R.x,R.y);
evs.pb({R,-1});
evs.pb({L,1});
if(L<R)cnt++;
}
int ans=cnt;
sort(evs.begin(),evs.end());
for(auto ev:evs){
cnt-=ev.second;
ans=min(ans,cnt);
}
printf("%i\n",ans);
return 0;
}
詳細信息
answer.code: In function ‘int main()’:
answer.code:170:30: error: no match for ‘operator-’ (operand type is ‘pt’)
170 | if(part(L))L=-L;
| ^~
In file included from /usr/include/c++/13/bits/stl_algobase.h:67,
from /usr/include/c++/13/algorithm:60,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
from answer.code:1:
/usr/include/c++/13/bits/stl_iterator.h:625:5: note: candidate: ‘template<class _IteratorL, class _IteratorR> decltype ((__y.base() - __x.base())) std::operator-(const reverse_iterator<_Iterator>&, const reverse_iterator<_IteratorR>&)’
625 | operator-(const reverse_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:625:5: note: template argument deduction/substitution failed:
answer.code:170:31: note: ‘pt’ is not derived from ‘const std::reverse_iterator<_Iterator>’
170 | if(part(L))L=-L;
| ^
/usr/include/c++/13/bits/stl_iterator.h:1800:5: note: candidate: ‘template<class _IteratorL, class _IteratorR> decltype ((__x.base() - __y.base())) std::operator-(const move_iterator<_IteratorL>&, const move_iterator<_IteratorR>&)’
1800 | operator-(const move_iterator<_IteratorL>& __x,
| ^~~~~~~~
/usr/include/c++/13/bits/stl_iterator.h:1800:5: note: template argument deduction/substitution failed:
answer.code:170:31: note: ‘pt’ is not derived from ‘const std::move_iterator<_IteratorL>’
170 | if(part(L))L=-L;
| ^
In file included from /usr/include/c++/13/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:127:
/usr/include/c++/13/complex:365:5: note: candidate: ‘template<class _Tp> std::complex<_Tp> std::operator-(const complex<_Tp>&, const complex<_Tp>&)’
365 | operator-(const complex<_Tp>& __x, const complex<_Tp>& __y)
| ^~~~~~~~
/usr/include/c++/13/complex:365:5: note: template argument deduction/substitution failed:
answer.code:170:31: note: ‘pt’ is not derived from ‘const std::complex<_Tp>’
170 | if(part(L))L=-L;
| ^
/usr/include/c++/13/complex:374:5: note: candidate: ‘template<class _Tp> std::complex<_Tp> std::operator-(const complex<_Tp>&, const _Tp&)’
374 | operator-(const complex<_Tp>& __x, const _Tp& __y)
| ^~~~~~~~
/usr/include/c++/13/complex:374:5: note: template argument deduction/substitution failed:
answer.code:170:31: note: ‘pt’ is not derived from ‘const std::complex<_Tp>’
170 | if(part(L))L=-L;
| ^
/usr/include/c++/13/complex:383:5: note: candidate: ‘template<class _Tp> std::complex<_Tp> std::operator-(const _Tp&, const complex<_Tp>&)’
383 | operator-(const _Tp& __x, const complex<_Tp>& __y)
| ^~~~~~~~
/usr/include/c++/13/complex:383:5: note: template argument deduction/substitution failed:
answer.code:170:31: note: candidate expects 2 arguments, 1 provided
170 | if(part(L))L=-L;
| ^
/usr/include/c++/13/complex:460:5: note: candidate: ‘template<class _Tp> std::complex<_Tp> std::operator-(const complex<_Tp>&)’
460 | operator-(const complex<_Tp>& __x)
| ^~~~~~~~
/usr/include/c++/13/complex:460:5: note: template argument deduction/substitution failed:
answer.code:170:31: note: ‘pt’ is not derived from ‘const std::complex<_Tp>’
170 | if(part(L))L=-L;
| ^
In file included from /usr/include/c++/13/valarray:605,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:166:
/usr/include/c++/13/bits/valarray_after.h:406:5: note: candidate: ‘template<class _Dom1, class _Dom2> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Expr, std::_Expr, _Dom1, _Dom2>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const _Expr<_Dom1, typename _Dom1::value_type>&, const _Expr<_Dom2, typename _Dom2::value_type>&)’
406 | _DEFINE_EXPR_BINARY_OPERATOR(-, struct std::__minus)
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/valarray_after.h:406:5: note: template argument deduction/substitution failed:
answer.code:170:31: note: ‘pt’ is not derived from ‘const std::_Expr<_Dom1, typename _Dom1::value_type>’
170 | if(part(L))L=-L;
| ^
/usr/include/c++/13/bits/valarray_after.h:406:5: note: candidate: ‘template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Expr, std::_Constant, _Dom, typename _Dom::value_type>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const _Expr<_Dom1, typename _Dom1::value_type>&, const typename _Dom::value_type&)’
406 | _DEFINE_EXPR_BINARY_OPERATOR(-, struct std::__minus)
| ...