QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#498272#7906. Almost ConvexSusie_RainTL 1ms4140kbC++203.5kb2024-07-30 10:55:322024-07-30 10:55:32

Judging History

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

  • [2024-07-30 10:55:32]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4140kb
  • [2024-07-30 10:55:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define debug(x) cout<<x<<"--------------------------------------\n" ;
const int N = 1e5 + 10;
typedef long long ll;
const int INF = 1e9 ;
const int MOD = 1e9 + 7 ;
typedef pair<int,int> PII ;
int gcd(int a,int b){
    return b ? gcd(b,a%b) : a ;
}
ll qpow(int a,int k){
    ll res = 1 ;
    while (k){
        if(k&1) res = 1ll * res * a % MOD ;
        a = 1ll * a * a % MOD ;
        k >>= 1 ;
    }
    return res ;
}
int n;
const double eps=1e-8;
const double PI=acos(-1);
inline int sgn(double x){
    return fabs(x)<eps?0:(x<0?-1:1);
}
struct point{
    double x,y;
    point(double a=0,double b=0):x(a),y(b){}
    point operator +(const point &A)const{
        return point(x+A.x,y+A.y);
    }
    point operator -(const point &A)const{
        return point(x-A.x,y-A.y);
    }
    point operator *(const double v)const{
        return point(x*v,y*v);
    }
    point operator /(const double v)const{
        return point(x/v,y/v);
    }
    bool operator ==(const point &A)const{
        return sgn(x-A.x)==0&&sgn(y-A.y)==0;
    }
    bool operator <(const point &A)const{
        if(fabs(x-A.x)<eps) return (x-A.x<-eps);
       return x-A.x<-eps;
    }
    double norm(){
        return sqrt(x*x+y*y);
    }
};
double dot(point a,point b){ // |A||B|cosθ
    return a.x*b.x+a.y*b.y;
}
double det(point a,point b){ // |A||B|sinΘ
    return a.x*b.y-a.y*b.x;
}
using Point = point;
using Points = vector<Point>;
double theta(auto p) { return atan2(p.y, p.x); } // 求极角
bool lt(double a,double b){
    return (a-b<-eps);
}
void psort(Points &ps, Point c = {})              // 极角排序
{
    sort(ps.begin(), ps.end(), [&](auto p1, auto p2) {
        return lt(theta(p1 - c), theta(p2 - c));
    });
}
std::vector<point> getHull(std::vector<point> p) {
    std::vector<point> h, l;
    std::sort(p.begin(), p.end(), [&](auto a, auto b) {
        if (a.x != b.x) {
            return a.x < b.x;
        } else {
            return a.y < b.y;
        }
    });
    p.erase(std::unique(p.begin(), p.end()), p.end());
    if (p.size() <= 1) {
        return p;
    }

    for (auto a : p) {
        while (h.size() > 1 && det(a - h.back(), a - h[h.size() - 2]) <= 0) {
            h.pop_back();
        }
        while (l.size() > 1 && det(a - l.back(), a - l[l.size() - 2]) >= 0) {
            l.pop_back();
        }
        l.push_back(a);
        h.push_back(a);
    }

    l.pop_back();
    std::reverse(h.begin(), h.end());
    h.pop_back();
    l.insert(l.end(), h.begin(), h.end());
    return l;
}
void solve(){
    cin >> n;
    Points a(n);
    for(int i=0;i<n;i++) cin >> a[i].x >> a[i].y;
    auto hull = getHull(a);
    map<point,bool> mp;
    for(auto x:hull) mp[x] = 1;
    vector<point> now;
    int ans = 1;
    for(int i=0;i<n;i++){ // 枚举点
        if(mp[a[i]]) continue;
        now.clear(); point o = a[i];
//        debug(1)
//        cout << o.x << ' ' << o.y << '\n';
        for(auto x:a){
            if(x==o) continue;
            now.push_back(x);
        }
        psort(now,o);
        int m = (int)now.size();
        for(int j=0;j<m;j++){
//            cout << now[j].x << ' ' << now[j].y << '\n';
            if(mp[now[j]]&&mp[now[(j+1)%m]]) ans ++;
        }
    }
    cout << ans << '\n';
}
signed main(){
    ios::sync_with_stdio(false) ;
    cin.tie(0) ;
    int tt = 1 ;
//    cin >> tt ;
    while (tt--) solve() ;
    return 0 ;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4140kb

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: 4140kb

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: 3720kb

input:

3
0 0
3 0
0 3

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 4100kb

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: 3784kb

input:

4
0 0
0 3
3 0
3 3

output:

1

result:

ok 1 number(s): "1"

Test #6:

score: -100
Time Limit Exceeded

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:


result: