QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#421815 | #3173. Cakey McCakeFace | juancs# | WA | 0ms | 3452kb | C++20 | 3.3kb | 2024-05-26 06:20:50 | 2024-05-26 06:20:50 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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: ''