QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#499757#7906. Almost ConvexSaviorWA 34ms4164kbC++208.0kb2024-07-31 18:53:412024-07-31 18:53:41

Judging History

你现在查看的是最新测评结果

  • [2024-07-31 18:53:41]
  • 评测
  • 测评结果:WA
  • 用时:34ms
  • 内存:4164kb
  • [2024-07-31 18:53:41]
  • 提交

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'