UVA 1396_UVC和UVA

UVA 1396_UVC和UVA书上的题目,开始跟着新的大神了==#include#include#include#includeusingnamespacestd;//精度控制constdoubleeps=1e-10;intdcmp(doublex){if(fabs(x)

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
书上的题目,开始跟着新的大神了= =

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

//精度控制
const double eps=1e-10;
int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    return x<0?-1:1;
}

//点
struct Point
{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
};

//向量
typedef Point Vector;

//点-点==向量
Vector operator-(Point A,Point B)
{
    return Vector(A.x-B.x,A.y-B.y);
}

//向量+向量==向量 或 点+向量==点
Vector operator+(Vector A,Vector B)
{
    return Vector(A.x+B.x,A.y+B.y);
}

//向量*实数==向量
Vector operator*(Vector A,double p)
{
    return Vector(A.x*p,A.y*p);
}

//求向量长度
double Length(Vector v)
{
    return sqrt(v.x*v.x+v.y*v.y);
}

//返回v逆时针旋转90度的单位向量
Vector Normal(Vector v)
{
    double L=Length(v);
    return Vector(-v.y/L, v.x/L);
}

//叉积
double Cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}

//直线
struct Line
{
    Point p;
    Vector v;
    double ang;
    Line(){}
    Line(Point p,Vector v):p(p),v(v)
    {
        ang=atan2(v.y,v.x);
    }
    bool operator<(const Line &L)const
    {
        return ang<L.ang;
    }
};

//判断p是否在直线L左边(在直线上不算)
bool OnLeft(Line L,Point p)
{
    return Cross(L.v,p-L.p)>0;
}

//得到直线的交点
Point GetIntersection(Line a,Line b)
{
    Vector u=a.p-b.p;
    double t=Cross(b.v,u)/Cross(a.v,b.v);
    return a.p+a.v*t;
}

//求直线集合L构成的半平面交集,如果存在是一个凸包
int HalfplaneIntersection(Line *L,int n,Point *poly)
{
    //极角排序
    sort(L,L+n);

    int first=0,last=0;
    Point *p=new Point[n];
    Line *q=new Line[n];
    q[0]=L[0];

    for(int i=1;i<n;i++)
    {
        //删除尾部无效节点
        while(first<last && !OnLeft(L[i],p[last-1])) last--;
        //删除头部无效节点
        while(first<last && !OnLeft(L[i],p[first])) first++;
        //插入新直线
        q[++last]=L[i];

        //如果新插入的直线与last直线平行,需要删除最右边的那条
        if(fabs(Cross(q[last].v,q[last-1].v))<eps)
        {
            last--;
            if(OnLeft(q[last],L[i].p)) q[last]=L[i];
        }

        //新插入直线与上一条直线构成last-1交点
        if(first<last) p[last-1]=GetIntersection(q[last-1],q[last]);
    }

    //同first直线排序尾部无效节点
    while(first<last && !OnLeft(q[first],p[last-1])) last--;

    //半平面不构成有界区域
    if(last-first<=1 ) return 0;

    //求首直线与尾直线交点
    p[last]=GetIntersection(q[last],q[first]);

    int m=0;
    for(int i=first;i<=last;i++) poly[m++]=p[i];
    return m;
}

const int N=101;
int n;
Point p[N],poly[N];
Vector v1[N],v2[N];
Line l[N];

int main()
{
    while(scanf("%d",&n)&&n){
        for(int i=0;i<n;i++){
            scanf("%lf%lf",&p[i].x,&p[i].y);
        }
        for(int i=0;i<n;i++){
            v1[i]=p[(i+1)%n]-p[i];
            v2[i]=Normal(v1[i]);
        }
        double left=0,right=1e8;
        while((right-left)>1e-7){
            double mid=(right+left)/2;
            for(int i=0;i<n;i++){
                l[i]=Line(p[i]+v2[i]*mid,v1[i]);
            }
            int m=HalfplaneIntersection(l,n,poly);
            if(!m)right=mid;
            else left=mid;
        }
        printf("%.6lf\n",left);
    }
    return 0;
}


















版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169945.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Python神级操作,还原已撤回的微信消息

    Python神级操作,还原已撤回的微信消息项目环境语言:Python3编辑器:Pycharm导包效果展示以下截图显示的撤回消息类型依次是文字消息、微信自带表情、图片、语音、定位地图、名片、公众号文章、音乐、视频。有群里撤回的,也有个人号撤回的。图文来源:http://kks.me/aULmF图文来源:http://kks.me/aULmF程序思路主要由两部分组成:handler_receiv…

  • 简洁优雅的Mac OS X软件安装体验 – homebrew-cask

    简洁优雅的Mac OS X软件安装体验 – homebrew-cask

  • 正则表达式用法简介与速查

    正则表达式用法简介与速查

  • springboot事务的传播机制[通俗易懂]

    springboot事务的传播机制[通俗易懂]事务的传播机制所谓事务的传播行为是指,如果在开始当前事务之前,一个事务上下文已经存在,此时有若干选项可以指定一个事务性方法的执行行为。(,默认)REQUIRED :如果当前存在事务,则加入该事务;如果当前没有事务,则创建一个新的事务。SUPPORTS :如果当前存在事务,则加入该事务;如果当前没有事务,则以非事务的方式继续运行。MANDATORY :如果当前存在事务,则加入该事务;如果当前没有事务,则抛出异常。REQUIRES_NEW :创建一个新的事务,如果当前存在事务,则把当前事务挂起。

  • nonzero函数_python 类方法

    nonzero函数_python 类方法类的nonzero方法用于将类转换为布尔值。通常在用类进行判断和将类转换成布尔值时调用。比如语句ifA:print'foo'中就会调用A.nonzero()来判断。下面这个程序应

  • vlan的作用和特点_VLAN的概念

    vlan的作用和特点_VLAN的概念VLAN它的全称是虚拟局域网,作用就是把连接在同一交换机下的主机分为更小的逻辑网段,以减少广播的数量,不同的VLAN之间不能通讯,这样广播就被限制在同一个业务需求主机的VLAN里,即便是连接在同一个交换机下,不同的VLAN也不会收到广播的ARP请求!如果他们之间需要通讯,只能借助路由器或三层交换机没有携带VLAN(Tag)的数据帧携带VLAN(Tag)的数据帧标签类型把同一物理局域网内的不同用户逻辑地划分成不同的广播域、有助于控制流量、减少设备投资、简化网络管理。提高网络的安全性。1)区段化:将一个网络

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号