QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#421815#3173. Cakey McCakeFacejuancs#WA 0ms3452kbC++203.3kb2024-05-26 06:20:502024-05-26 06:20:50

Judging History

This is the latest submission verdict.

  • [2024-05-26 06:20:50]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3452kb
  • [2024-05-26 06:20:50]
  • Submitted

answer

#include <bits/stdc++.h>
#define el '\n'
#define forn(i, n) for(int i = 0; i < (int)n; ++i)
#define for1(i, n) for(int i = 1; i <= (int)n; ++i)
#define fore(i, l, r)for(int i = l; i <= (int)r; ++i)
#define fored(i, l, r)for(int i = r; i <= (int)l; --i)
#define all(a) a.begin(), a.end()
#define d(x) cerr<<#x<<" "<<x<<el
#define sz(x) x.size()
#define pb push_back
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef array<int, 4> a4;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;

const int nax = 1e4 + 100;
const ld inf = 1e20;
struct pt{
    ll x, y;
    pt(){}
    pt(ll x,ll y):x(x),y(y){}
    ll operator%(pt p){return x * p.y - y * p.x;}
    ll operator*(pt p){return x * p.x + y * p.y;}
    pt operator-(pt p){return {x - p.x, y-p.y};}
    ll norm2(){return *this**this;}
    ld norm(){return sqrt(norm2());}
    bool operator<(pt p)const{
        return x == p.x ? y < p.y : x < p.x;
    }
    bool operator ==(pt p)const{
        return x == p.x && y == p.y;
    }
    ll side(pt p, pt q){return (q-p) % (*this-p);}

};
const ld one = 1.0;
struct line
{
    pt v; ll c;
    line(){}
    line(pt p, pt q):v(q-p), c(v%p){}
    ll side(pt p){return v%p -c;}
    ld dist(pt p){assert(v.norm2() != 0); return abs(one*side(p) / v.norm2());}
    ld distReal(pt p){return abs(one*side(p) / v.norm());}
};

vector<pt> chull(vector<pt> &p){
    if(sz(p) < 3) return p;
    vector<pt> r;
    sort(all(p));
    forn(i,sz(p)){
        while(sz(r) > 1 && r.back().side(r[sz(r)-2], p[i])>=0) r.pop_back();
        r.pb(p[i]);
    }
    r.pop_back();
    int k = sz(r);
    fored(i, 0, sz(p) -1){
        while(sz(r) > k + 1 &&r.back().side(r[sz(r)-2], p[i])>=0) r.pop_back();
        r.pb(p[i]);
    }
    r.pop_back();
    return r;
}

ld solve(vector<pt> &pts){
    int n = sz(pts);
    int j = -1;
    ld minDist = -inf;
    line curline(pts[0], pts[1]);
    line minLine = curline;
    int minInd = -1;
    d(n);
    fore(i,2,n-1){
        ld di = curline.dist(pts[i]);
        d(di);
        if(j == -1 || di > curline.dist(pts[j])){
            j = i;
        }
    }
    minInd = j;
    d(minInd);
    d(minDist);

    fore(i,2, n-1){
        curline = line(pts[i], pts[(i+1) % n]);
        while(curline.dist(pts[(j-1+n)%n]) > curline.dist(pts[j]) || curline.dist(pts[(j+1)%n]) > curline.dist(pts[j]) ){
            if(curline.dist(pts[(j-1+n)%n]) > curline.dist(pts[(j+1+n)%n])){
                j = (j-1+n)%n;
            }else{
                j = (j + 1) % n;
            }
        }
        ld di = curline.dist(pts[j]) ;
        if(di < minDist){
            minDist = di;
            minLine = curline;
            minInd = j;
        }
    }
    assert(minInd != -1);
    return minLine.distReal(pts[minInd]);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int n, r;
    cin >> n >> r;
    vector<pt> pts(n);
    forn(i,n){
        int x,y;
        cin>>x>>y;
        pts[i] = {x,y};
    }
    sort(all(pts));

    vector<pt> ch = chull(pts);
    d(sz(ch));
    for(auto [x,y] : ch){
        cout<<x<<" "<<y<<")"<<el;
    }
    // ch.erase(unique(all(ch)), ch.end());
    // ld ans = solve(ch);
    // cout<<ans<<el;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3452kb

input:

5
5
0 10 12 20 30
1 5 17 27 50

output:


result:

wrong answer 1st lines differ - expected: '5', found: ''