QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#313977 | #784. 旋转卡壳 | nmmCampPTCP | 0 | 0ms | 0kb | C++17 | 5.5kb | 2024-01-25 10:59:37 | 2024-01-25 10:59:39 |
Judging History
你现在查看的是最新测评结果
- [2024-10-16 12:18:36]
- hack成功,自动添加数据
- (/hack/1005)
- [2024-09-24 16:55:39]
- hack成功,自动添加数据
- (/hack/888)
- [2024-07-31 21:52:32]
- hack成功,自动添加数据
- (/hack/764)
- [2024-07-31 21:47:53]
- hack成功,自动添加数据
- (/hack/763)
- [2024-05-30 09:00:15]
- hack成功,自动添加数据
- (/hack/642)
- [2024-01-25 10:59:37]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
using LD = long double;
constexpr LD eps = 1e-12;
const LD PI = acos(-1);
LD sgn(LD x){
if(fabs(x) < eps) return 0;
else return x>0 ? 1 : -1;
}
#define lt(x,y) (sgn((x)-(y)) < 0)
#define eq(x,y) (sgn((x)-(y)) == 0)
#define gt(x,y) (sgn((x)-(y)) > 0)
#define sqr(x) ((x)*(x))
//点的定义
struct pt{
LD x,y;
pt(LD x=0, LD y=0):x(x), y(y){};
bool operator==(const pt& o){
return sgn(x-o.x)==0 and sgn(y-o.y)==0; //这里不能用not运算,非整数
}
bool operator!=(const pt& o){
return !(*this == o);
}
pt operator+(const pt& o) const {
return {x+o.x, y+o.y};
}
pt operator-(const pt& o) const {
return {x-o.x, y-o.y};
}
pt operator*(LD c){
return {x*c, y*c};
}
pt operator/(LD c){
assert(c!=0);
return {x/c, y/c};
}
pt operator+=(const pt& o){
*this = *this + o;
}
pt operator-=(const pt& o){
*this = *this - o;
}
};
LD dis(pt a, pt b){
return hypot(a.x-b.x, a.y-b.y);
}
//向量定义
typedef pt vec;
LD dot(vec a, vec b){
return a.x*b.x + a.y*b.y;
}
LD cross(vec a, vec b){
return a.x*b.y - a.y*b.x;
}
LD len(vec v){
return sqrt(sqr(v.x) + sqr(v.y));
}
bool parallel(vec a, vec b){
return sgn(cross(a, b)) == 0;
}
vec normalize(vec v){
return v/len(v);
}
vec rotate(vec v, LD rad){
return {v.x*cos(rad)-v.y*sin(rad), v.x*sin(rad)+v.y*cos(rad)};
}
vec rotate90(vec v){
return {-v.y, v.x};
}
LD v_ang(vec a, vec b){
return acos(dot(a,b)/len(a)/len(b));
}
LD tri_area(pt a, pt b, pt c){
return fabs(cross(b-a, c-a)/2);
}
int qua(pt p){
auto [x,y] = p;
if(x > 0 and y >= 0) return 1;
if(x <= 0 and y > 0) return 2;
if(x < 0 and y <= 0) return 3;
if(x >= 0 and y < 0) return 4;
return 0;
}
bool cmp(pt x, pt y){
return qua(x)<qua(y) or qua(x) == qua(y) and gt(cross(x,y), 0); //叉乘为正,说明x到y为逆时针
}
vector<pair<int, int>>v[2];
vector<pt> mkv(vector<vector<pt>> a){
for(int i = 0; i<2; ++i){
a[i].emplace_back(a[i].front());
}
int i[2] = {0, 0},
len[2] = {(int)a[0].size()-1, (int)a[1].size()-1};
vector<pt>ret;
vector<vec>e[2];
for(int x = 0; x<2; ++x){
for(int j = 1; j<a[x].size(); ++j){
e[x].emplace_back(a[x][j]-a[x][j-1]);
}
}
ret.emplace_back(a[0][0] + a[1][0]);
do{
int d = sgn(cross(a[1][i[1]+1] - a[1][i[1]],
a[0][i[0]+1] - a[0][i[0]])) >= 0;
ret.emplace_back(a[d][i[d]+1] - a[d][i[d]] + ret.back());
// if(a[d][i[d]+1]-a[d][i[d]] != e[d][i[d]]){
// cout << "diff=" << ' ' << i[d] << ' ';
// }
v[1].emplace_back(d, i[d]);
i[d] = (i[d]+1) % len[d];
} while(i[0] or i[1]);
return ret;
}
//int db1, db2, db3, db4;
vector<pt> minkovski(vector<pt> h1, vector<pt> h2){ //首尾相连,有封闭点(多余的p[0])
vector<pt>res {h1[0]+h2[0]};
h1.emplace_back(h1.front()), h2.emplace_back(h2.front());
vector<vec>e1, e2;
//n, m 分别为原凸包 A/B 的点集大小
for(int i = 1; i<h1.size(); ++i) e1.emplace_back(h1[i]-h1[i-1]);
for(int i = 1; i<h2.size(); ++i) e2.emplace_back(h2[i]-h2[i-1]);
// db1 = e1.size();
// db2 = e2.size();
cout << "esize=" << e1.size() << ' ' << e2.size() << '\n';
int n = h1.size()-1, m = h2.size()-1;
int p1 = 0, p2 = 0;
while(p1 < n and p2 < m){
auto cur = res.back();
if(sgn(cross(e1[p1], e2[p2])) >= 0) v[0].emplace_back(0, p1), cur += e1[p1++];
else v[0].emplace_back(1, p2), cur += e2[p2++];
res.emplace_back(cur);
}
while(p1 < n) v[0].emplace_back(0, p1), res.emplace_back(res.back()+e1[p1++]);
while(p2 < m) v[0].emplace_back(1, p2), res.emplace_back(res.back()+e2[p2++]);
return res; //返回的为非严格凸包
}
void rotate(vector<pt>& v){
auto p = min_element(v.begin(), v.end(), [](auto p1, auto p2){
return p1.y < p2.y or p1.y == p2.y and p1.x < p2.x;
})-v.begin();
for(int i = 0; i<p; ++i) v.emplace_back(v[i]);
v.erase(v.begin(), v.begin()+p);
}
int main(){
int n; cin >> n;
vector<pt>ps(n), fps(n);
for(int i = 0; i<n; ++i){
cin >> ps[i].x >> ps[i].y;
fps[i] = pt{0,0}-ps[i];
}
rotate(ps), rotate(fps);
// ps.emplace_back(ps[0]), fps.emplace_back(fps[0]);
auto M1 = minkovski(ps, fps);
auto M2 = mkv({ps, fps});
// cout << M1.size() << '/' << M2.size() << '\n';
// assert(M1.size() == M2.size());
// for(int i = 0; i<M1.size(); ++i){
// if(M1[i] != M2[i]) {
// cout << i << ' ' << M1[i].x << ' ' << M1[i].y << ' ' << M2[i].x << ' ' << M2[i].y << '\n';
// break;
// }
if(v[0].size() != v[1].size()){
cout << v[0].size() << ' ' << v[1].size() << '\n';
cout << "opns\n";
}
else{
cout << "opsize= " << v[0].size() << '\n';
for(int i = 0; i<v[0].size(); ++i){
if(v[0][i] != v[1][i]){
cout << i << ' ' << v[0][i].first << ' ' << v[0][i].second << ' ' << v[1][i].first << ' ' << v[1][i].second << '\n';
break;
}
}
}
LD ans = 0;
cout << M1.size() << ' ' << M2.size() << '\n';
for(int i = 0; i<M1.size(); ++i){
ans = max(ans, len(M1[i]));
}
cout << fixed << setprecision(10) << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
1000 0 0 -997615 -8573 -1988394 -28911 -2726572 -44296 -3491635 -60392 -4419752 -82814 -5298550 -105946 -5723430 -118453 -6608257 -147267 -7034966 -161982 -7563964 -181682 -8507871 -222865 -9499799 -271846 -10090186 -303547 -10400262 -322989 -10614073 -339725 -11081438 -378596 -11791568 -439127 -127...
output:
result:
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%