QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#499757 | #7906. Almost Convex | Savior | WA | 34ms | 4164kb | C++20 | 8.0kb | 2024-07-31 18:53:41 | 2024-07-31 18:53:41 |
Judging History
answer
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
#define int long long
#define double long double
using ll = long long;
const int N=1e3+5,inf=1e18,mod=1e9+7;
const double eps=0;
typedef pair<int,int>P;
int sgn(double x){ //符号
if(abs(x)<=eps)return 0;
if(x>0)return 1;
return -1;
}
struct Point{ //点与向量
double x,y;
Point(){}
Point(double x,double y):x(x),y(y){}
bool operator==(const Point&a)const{
return (sgn(x-a.x)==0&&sgn(y-a.y)==0);
}
bool operator<(const Point&a)const{
if(sgn(x-a.x)==0)return sgn(y-a.y)==-1;
return sgn(x-a.x)==-1;
}
bool operator>(const Point&a)const{return !((*this<a)||(*this==a));}
Point operator+(const Point&a)const{return {x+a.x,y+a.y};}
Point operator-(const Point&a)const{return {x-a.x,y-a.y};}
Point operator-()const{return {-x,-y};}
Point operator*(double t)const{return {x*t,y*t};}
void input(){cin>>x>>y;}
double dot(const Point&a)const{return x*a.x+y*a.y;} //点积
double cross(const Point&a)const{return x*a.y-y*a.x;} //叉积
double len2()const{return dot(*this);} //长度平方
double len()const{return sqrt(len2());} //长度
int toleft(const Point&a)const{return sgn(cross(a));} //当前向量到 a 是逆时针旋转
double dis2(const Point&a)const{return ((*this)-a).len2();} //两点距离平方
double dis(const Point&a)const{return sqrt(dis2(a));} //两点距离
double ang(const Point&a)const{ //两向量夹角
return acos(max(-1.0l,min((dot(a)/(len()*a.len())),1.0l)));
}
double ang()const{return atan2(y,x);}
Point rot(const double&rad)const{
return{x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad)};
}
};
typedef Point Vector;
struct Line{
Point p;
Vector v;
Line(){}
Line(Point p,Vector v):p(p),v(v){}
double dis(Point a)const{return abs(v.cross(a-p)/v.len());}
Point inter(const Line&a)const{
return p+v*((a.v.cross(p-a.p))/(v.cross(a.v)));
}
bool operator<(const Line&a)const{
if(sgn(atan2(v.y,v.x)-atan2(a.v.y,a.v.x))==0)return (a.p-p).cross(a.p+a.v-p)>0;
else return atan2(v.y,v.x)<atan2(a.v.y,a.v.x);
}
};
struct Polygon{
vector<Point> p;
int nxt(const int x)const{return x==(p.size()-1)?0:(x+1);}
int pre(const int x)const{return x==0?(p.size()-1):(x-1);}
double area()const{
double sum=0;
for(int i=0;i<p.size();i++)
sum+=p[i].cross(p[nxt(i)]);
return sum/2;
}
double circ()const{
double sum=0;
for(int i=0;i<p.size();i++)
sum+=p[i].dis(p[nxt(i)]);
return sum;
}
};
Polygon Cross(vector<Line>vec){
sort(vec.begin(),vec.end());
deque<Line>dq;
vector<Line>v;
for(auto line:vec){
if(v.empty() || sgn(atan2(v.back().v.y,v.back().v.x)- atan2(line.v.y,line.v.x))!=0)v.push_back(line);
}
auto illegal=[&](Point p,Line l){return (l.p-p).cross(l.p+l.v-p)<0;};
for(auto line:v){
while(dq.size()>=2 && illegal(dq.back().inter(dq.at(dq.size()-2)),line))dq.pop_back();
while(dq.size()>=2 && illegal(dq.front().inter(dq.at(1)),line))dq.pop_front();
dq.push_back(line);
}
while(dq.size()>=2 && illegal(dq.back().inter(dq.at(dq.size()-2)),dq.front()))dq.pop_back();
while(dq.size()>=2 && illegal(dq.front().inter(dq.at(1)),dq.back()))dq.pop_front();
vector<Point>ans;
for(int i=0;i<dq.size();i++){
ans.push_back(dq.at(i).inter(dq.at((i+1)%dq.size())));
}
Polygon res;
res.p=ans;
return res;
}
struct Segment{ //线段
Point a,b;
Segment(){}
Segment(Point a,Point b):a(a),b(b){}
bool operator<(const Segment &s)const{ //按左端点横坐标排序
return make_pair(a,b)<make_pair(s.a,s.b);
}
double dis(const Point&p)const{ //点到线段距离
if(sgn((p-a).dot(b-a))==-1||sgn((p-b).dot(a-b))==-1)return min(p.dis(a),p.dis(b));
Point p0=a,v=b-a;
return abs(v.cross(p-p0)/v.len());
}
// 判断点是否在线段上
// -1 点在线段端点 | 0 点不在线段上 | 1 点严格在线段上
int is_on(const Point&p)const{
if(p==a || p==b)return -1;
return (p-a).toleft(p-b)==0 && (p-a).dot(p-b)<-eps;
}
};
struct Convex:Polygon{ //凸多边形
double Calipers()const{ //凸包直径 (旋转卡壳)
double ans=0;
if(p.size()==2)return p[0].dis(p[1]);
int now=0;
for(int i=0;i<p.size();i++){
Line l(p[i],p[i]-p[nxt(i)]);
while(l.dis(p[now])<=l.dis(p[nxt(now)]))now=nxt(now);
ans=max(ans,max(p[i].dis(p[now]),p[nxt(i)].dis(p[now])));
}
return ans;
}
// O(logn) 判断点是否在凸包内
// -1 点在凸包边上 | 0 点在凸包外 | 1 点在凸包内
int is_in(const Point a)const{
if(p.size()==1)return a==p[0]?-1:0;
if(p.size()==2)return Segment(p[0],p[1]).is_on(a)?-1:0;
if(a==p[0])return -1;
if((p[1]-p[0]).toleft(a-p[0])==-1 || (p.back()-p[0]).toleft(a-p[0])==1)return 0;
auto cmp=[&](const Point&u,const Point&v){
return (u-p[0]).toleft(v-p[0])==1;
};
int pos=lower_bound(p.begin()+1,p.end(),a,cmp)-p.begin();
if(pos==1)return Segment(p[0],p[1]).is_on(a)?-1:0;
if(pos==p.size()-1 && Segment(p[0],p[pos]).is_on(a))return -1;
if(Segment(p[pos-1],p[pos]).is_on(a))return -1;
return (p[pos]-p[pos-1]).toleft(a-p[pos-1])>0;
}
};
Convex Andrew(vector<Point> p) { //nlogn求凸包
vector<Point> st;
Convex ans;
if(p.empty()){
ans.p=st;
return ans;
}
sort(p.begin(),p.end());
auto check=[](const vector<Point>&st,Point u){
Point tmp1=st.back(),tmp2=*prev(st.end(),2);
return (tmp1-tmp2).toleft(u-tmp1)<=0; // < 边上有点 , <= 边上没点
};
for(auto u:p){
while(st.size()>1&&check(st,u))
st.pop_back();
st.push_back(u);
}
int k=st.size();
p.pop_back(); // 下凸壳最后一点和上凸壳起始点重复
reverse(p.begin(), p.end());
for(auto u:p){
while(st.size()>k&&check(st,u))
st.pop_back();
st.push_back(u);
}
st.pop_back(); // 上凸壳最后一点和下凸壳起始点重复
ans.p=st;
return ans;
}
void solve(){
int n;cin>>n;
vector<Point>arr(n);
for(int i=0;i<n;i++)
cin>>arr[i].x>>arr[i].y;
auto res=Andrew(arr);
set<P>st;
for(auto it:res.p) st.insert({it.x,it.y});
vector<int>sq;
for(int i=0;i<n;i++){
int x=arr[i].x,y=arr[i].y;
auto p=st.lower_bound({x,y});
if(p==st.end()) sq.push_back(i);
else if(p!=st.end()&&(!(p->first==x&&p->second==y))) sq.push_back(i);
}
//for(auto it:sq) cout<<arr[it].x<<' '<<arr[it].y<<endl;
//cout<<111<<endl;
int ans=0;
int tt=res.p.size();
for(int i=0;i<tt;i++){
int p1=i,p2=(i+1)%tt;
vector<array<double,2>>tmp;
vector<double>so1,so2;
Point c1=res.p[p2]-res.p[p1];
for(auto&it:sq){
Point a=arr[it]-res.p[p1],b=arr[it]-res.p[p2];
tmp.push_back({-a.ang(c1),b.ang(c1)});
}
int sz=tmp.size();
sort(tmp.begin(),tmp.end());
set<double>cl;
for(int j=0;j<=sz-1;j++){
if(cl.empty()) cl.insert(-tmp[j][1]),ans++;
else{
auto pp=cl.lower_bound(-tmp[j][1]);
if(pp==cl.end()) ans++;
cl.insert(-tmp[j][1]);
}
}
}
cout<<ans+1<<endl;
return;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int t=1;//cin>>t;
while(t--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3672kb
input:
7 1 4 4 0 2 3 3 1 3 5 0 0 2 4
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
5 4 0 0 0 2 1 3 3 3 1
output:
5
result:
ok 1 number(s): "5"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
3 0 0 3 0 0 3
output:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3768kb
input:
6 0 0 3 0 3 2 0 2 1 1 2 1
output:
7
result:
ok 1 number(s): "7"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
4 0 0 0 3 3 0 3 3
output:
1
result:
ok 1 number(s): "1"
Test #6:
score: -100
Wrong Answer
time: 34ms
memory: 4164kb
input:
2000 86166 617851 383354 -277127 844986 386868 -577988 453392 -341125 -386775 -543914 -210860 -429613 606701 -343534 893727 841399 339305 446761 -327040 -218558 -907983 787284 361823 950395 287044 -351577 -843823 -198755 138512 -306560 -483261 -487474 -857400 885637 -240518 -297576 603522 -748283 33...
output:
18950
result:
wrong answer 1st numbers differ - expected: '718', found: '18950'