VK Cup 2017 B. Volatile Kite （Div . 1）（凸多边形退化）（计算几何）

网友投稿 641 2022-08-24

VK Cup 2017 B. Volatile Kite （Div . 1）（凸多边形退化）（计算几何）

VK Cup 2017 B. Volatile Kite （Div . 1）（凸多边形退化）（计算几何）

题目链接：

​​即不能退化为凹多边形。

题解：

如果想要一个凸多边形不退化为凹多边形，当一个点A和它相连的两个点B、 C退化为成一条直线的时候就不行了，那么在极限的情况下，任意的相邻的三个点必然最多形成一条直线。因此我们可以求出点 i - 1和 i + 1的直线向量，再求点 i到这条直线的距离，再除以2，其实就是三角形的高 / 2。再取这些答案中最小的一个值。

AC代码：

#pragma comment(linker, "/STACK:102400000,102400000")#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair pii;typedef vector vi;const double eps = 1e-8; const int INF = 1e9+7; const ll inf =(1LL<<62) ;const int MOD = 1e9 + 7; const ll mod = (1LL<<32);const int N =1e6+6; const int M=100010;const int maxn=1001;#define mst(a) memset(a, 0, sizeof(a))#define M_P(x,y) make_pair(x,y)#define pi acos(-1.0)#define in freopen("in.txt","r",stdin) #define rep(i,j,k) for (int i = j; i <= k; i++) #define per(i,j,k) for (int i = j; i >= k; i--) #define lson x << 1, l, mid #define rson x << 1 | 1, mid + 1, r const int lowbit(int x) { return x&-x; }int read(){ int v = 0, f = 1;char c =getchar();while( c < 48 || 57 < c ){if(c=='-') f = -1;c = getchar();}while(48 <= c && c <= 57) v = v*10+c-48, c = getchar();return v*f;}mapmp;struct Point{ double x,y; Point(double x=0,double y=0):x(x),y(y) {}}p[1000010];typedef Point point;point operator -(Point a,Point b){ return point(a.x-b.x,a.y-b.y);}point operator +(Point a,Point b){ return point(a.x+b.x,a.y+b.y);}point operator *(Point a,double t){ return point(a.x*t,a.y*t);}point operator /(Point a,double t){ return point(a.x/t,a.y/t);}bool operator < (const Point &a,const Point &b){ return a.y0) return lentgh(v3); else return fabs(cross(v1,v2))/lentgh(v1); }int n;int main(){ scanf("%d",&n); for(int i = 1; i <= n; ++i) scanf("%lf%lf",&p[i].x,&p[i].y); double ans = inf; for(int i=1;i<=n;i++) { int last = i-1; int Next = i+1; if(last == 0) last = n; if(Next==n+1) Next = 1; ans = min(distancetoseg(p[i],p[Next],p[last])/2.0,ans); } printf("%.10f\n",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：代码
上一篇:快速幂取模
下一篇:成为Web开发人员的7个简单步骤（一个完整的web开发流程）
相关文章

 发表评论

暂时没有评论，来抢沙发吧~