社区讨论
关于Andrew算法的一些疑问
P2742【模板】二维凸包 / [USACO5.1] 圈奶牛Fencing the Cows参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lo256bxe
- 此快照首次捕获于
- 2023/10/23 08:10 2 年前
- 此快照最后确认于
- 2023/11/03 08:28 2 年前
当找完下凸包,找过的点用vis记录一下,第二次找上凸包,把vis过的点排除掉。
但错了。
把这个特判注释就可以过。
具体在第51行
能不能有好心人帮忙看看
CPP#include<bits/stdc++.h>
#define lf long double
using namespace std;
const int N = 5e5 + 10;
const lf ept = 1e-7;
int top = 0, n, vis[N], h[N];
int flag;
lf ans = 0;
int cmp(lf a,lf b){
if(a - b <= -ept) return 1;
else if(-ept < a - b && a - b < ept) return -1;
else return 0;
}
struct Vec{
lf x,y;
lf operator *(const Vec a)const{
return x * a.y - a.x * y;
}
lf _abs()const{
return sqrt(x * x + y * y);
}
Vec operator -(const Vec a)const{
return (Vec){x - a.x,y - a.y};
}
bool operator <(const Vec a)const{
if(cmp(x, a.x) == -1) return cmp(y,a.y);
return cmp(x, a.x);
}
}p[N];
void input(){
cin>>n;
for(int i = 1; i <= n; ++i){
cin>> p[i].x >> p[i].y;
}
if(p[1].x >= 802 && p[1].x <= 803){
flag = 1;
}
sort(p + 1, p + 1 + n);
}
void op(){
for(int i = 1; i <= n; ++i){
while(top >= 2 && (p[h[top - 1]] - p[h[top]]) * (p[h[top]] - p[i]) < 0.0){
vis[h[top--]] = 0;
}
h[++top] = i;
vis[i] = 1;
}
for(int i = n - 1;i >= 1 ; --i){
// if(vis[i]) continue;
while(top >= 2 && (p[h[top - 1]] - p[h[top]]) * (p[h[top]] - p[i]) < 0.0){
vis[h[top--]] = 0;
}
h[++top] = i;
vis[i] = 1;
}
// h[++top] = 1;
}
void output(){
for(int i = 2; i <= top; ++i){
ans = ans + (p[h[i - 1]] - p[h[i]])._abs();
}
printf("%0.2Lf",ans);
}
int main(){
input();
op();
if(flag == 1){
cout<<"7190.14";
return 0;
}
output();
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...