HDU 1392 Surround the Trees(凸包)
The HDU Trees 凸包
2023-09-11 14:14:41 时间
题面
懒得粘贴了。。。
大致题意:坐标系内有若干个点,问把这些点都圈起来的最小凸包周长。
题解
直接求出凸包,统计一遍答案即可
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
#define MAX 10000
#define INF 1000000000
int n,top;
struct Node
{
int x,y;
}p[MAX],S[MAX];
inline int read()
{
int x=0,t=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-'){t=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*t;
}
inline bool cmp(Node a,Node b)
{
double A=atan2((a.y-p[1].y),(a.x-p[1].x));
double B=atan2((b.y-p[1].y),(b.x-p[1].x));
if(A!=B)return A<B;
else return a.x<b.x;
}
long long Cross(Node a,Node b,Node c)
{
return 1LL*(b.x-a.x)*(c.y-a.y)-1LL*(b.y-a.y)*(c.x-a.x);
}
void Get()
{
p[0]=(Node){INF,INF};int k;
for(int i=1;i<=n;++i)
if(p[0].y>p[i].y||(p[0].y==p[i].y&&p[i].x<p[0].x))
{p[0]=p[i];k=i;}
swap(p[k],p[1]);
sort(&p[2],&p[n+1],cmp);
S[0]=p[1],S[1]=p[2];top=1;
for(int i=3;i<=n;)
{
if(top&&Cross(S[top-1],p[i],S[top])>=0)top--;
else S[++top]=p[i++];
}
}
inline double Dis(Node a,Node b)
{
return sqrt(1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y));
}
inline void GetAns()
{
double Ans=0;
if(top==0)
Ans=0;
else
if(top==1)
Ans=Dis(S[0],S[1]);
else
{
S[++top]=S[0];
for(int i=0;i<top;++i)
Ans+=Dis(S[i],S[i+1]);
}
printf("%.2f\n",Ans);
}
int main()
{
while(233333)
{
n=read();
if(!n)break;
for(int i=1;i<=n;++i)
p[i]=(Node){read(),read()};
Get();
GetAns();
}
return 0;
}
相关文章
- HTTP Status 500 - The absolute uri: http://java.sun.com/jsp/jstl/core cannot be resolved in either web.xml or the jar files deployed with this application
- java错误:The superclass "javax.servlet.http.HttpServlet" was not found on the Java Bu
- [Python] Create a minimal website in Python using the Flask Microframework
- [React Router v4] Render Multiple Components for the Same Route
- [RxJS] Implement the `map` Operator from Scratch in RxJS
- [Recompose] Set the HTML Tag of a Component via a Prop using Recompose
- Unexpected XML declaration. The XML declaration must be the first node in the document and no white
- 【35.43%】【hdu 4347】The Closest M Points
- initializeCachedDB function in JavaScript - how is the call delegated to
- The specified Android SDK Build Tools version (29.0.0) is ignored, as it is below the minimum suppor
- 解决The type or namespace name 'XXXX' does not exist in the namespace 'XXXXXXXXX' 的错误
- DL:深度学习算法(神经网络模型集合)概览之《THE NEURAL NETWORK ZOO》的中文解释和感悟(二)
- 成功解决LookupError: Resource [93maveraged_perceptron_tagger[0m not found. Please use the NLTK Downl
- ERROR Unable to validate credentials inherited from the shell environment: Invalid credentials
- 解决 Virtualbox 6.1.34 出现 End kernel panic - not syncing: attempted to kill the idle task
- (hdu step 7.2.1)The Euler function(欧拉函数模板题——求phi[a]到phi[b]的和)
- 【雅思】The English We Speak
- HDU ACM 1071 The area 定积分计算
- HDU 1598 find the most comfortable road (最小生成树) >>
- [TroubleShootin]The backup set holds a backup of a database other than the existing 'xxdb' database.
- 【问题解决】The connection to the server localhost:8080 was refused
- 兔子--Calling startActivity() from outside of an Activity context requires the FLAG_ACTIVITY_NEW_TASK
- HDU 1027 Ignatius and the Princess II 选择序列题解
- 解决办法:错误异常The superclass "javax.servlet.http.HttpServlet" was not found on the Java Build Path
- Warning:detected "cgroupfs" as the Docker cgroup driver. The recommended driver is "systemd".
- Accidental override: The following declarations have the same JVM signature (getWindow()Landroid/vie
- Be aware, overflowing tokens are not returned for the setting you have chosen