dtcms模板 协程 测试用例 Java Spring silverlight fonts jQuery Mobile 郑州网站建设 jq触发点击事件 linux查看mysql进程 ie内核浏览器怎么设置 oracle删除表字段 linux 获取系统时间 edate函数的使用方法 centos7安装gcc ubuntu更改文件夹权限 python相对路径怎么写 mysql时间戳转换日期 python数据类型 python网络编程 python中str函数 python包 python正则替换 java数组 java特性 java删除数组中的某个元素 bcdautofix flash相册制作 subprocess 挑战程序设计竞赛 mp4剪切合并大师 widcomm grep正则表达式 lol世界第一 js对象转字符串 浣海之核 mysql关联查询 脚本模板 情头污系 达芬奇resolve
当前位置: 首页 > 学习教程  > 编程语言

2019 ICPC Asia Nanjing Regional K.Triangle(求一个能将三角形分成两个面积相同的线段、计算几何)

2020/10/8 20:31:19 文章标签:

整理的算法模板合集&#xff1a; ACM模板 K.Triangle 用板子判断点是否在线段上即可。紫书的板子有点问题&#xff0c;判断是否在线段上的时候应该是<才能A&#xff0c;书上是 < … 对于第二问我们先特判一下特殊的情况&#xff0c;也就是p点在三角形端点的时候答案就是…

整理的算法模板合集: ACM模板


K.Triangle
在这里插入图片描述
用板子判断点是否在线段上即可。紫书的板子有点问题,判断是否在线段上的时候应该是<=才能A,书上是 < …
对于第二问我们先特判一下特殊的情况,也就是p点在三角形端点的时候答案就是端点对边的中点。

然后我们用一个直线玩一下三角形就发现,从特殊的情况(端点到对边中点)出发,我们假设端点是A,当p点在线段AB上的时候,若P点靠近A点,那么我们的直线就会转到靠近B点,当P点靠近B点的时候,我们的直线就会转到靠近C点,因为情况不定,所以我们可以将点换到都是在AB上的情况。(我们直接判断然后swap就行了,不会影响最终的答案)。将各种情况统一了以后才能编码解决嘛。

我们统一了以后,考虑如何找到这个点使得线段PQ可以均分大三角形的面积,直接枚举找答案肯定是不可取的,我们发现这个直线转动可能有单调性,求解最终的答案,考虑二分答案。我们直接二分点Q距离C点的距离,这样线段就会把整个三角形分成了一个小三角形和一个四边形,我们可以很轻松地求得小三角形的面积,轻松判断小三角形的面积是否为大三角形的面积的一半,所以答案的解法就出来了, 我们考虑二分答案,先用海伦公式求大三角形的面积,然后根据s = absinc/2可以求得角B的大小,然后继续用这个公式求小三角形的面积,比较是否等于大三角形的面积的一半,二分出答案以后我们要求该点的坐标,因为是在三角形上,我们可以直接按照比例,BC边与BQ边的长度之比,求得Q点的坐标。(我们这里B和C谁在左谁在右都无所谓,我们直接用B的坐标-C的坐标,按比例缩小了以后,直接加上C的坐标,这样C在左边差就是正数,C往右移(B的方向),C在右边差就是负数,C往左移动(B的方向))。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<bitset>
#include<queue>
#include<cmath>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;//卡精度
typedef pair<int,int> PII;

const int N = 3e4+7, M = 3e5 + 7;
const ll mod = 1e9+7;
const ll INF = 1e15+7;
const double eps = 1e-8;//可近似为趋近为 0 可以根据定义求导时使用
const int base = 131;//base = 13331 // hash
int t, n, m;
//判断点是否在直线上/线段2.7
//在三角形的三个线段上寻找另一个点连接的直线将三角形切开成两块面积相等
double ac, ab, bc, pa, pb, pc, ap, bp;
double area, sina, sinb, sinc;

struct Point
{
    double x, y;
    Point(double x = 0, double y = 0):x(x), y(y){ }
}a, b, c, p, q;

typedef Point Vector ;

Vector operator + (Vector a, Vector b)
{
    return Vector(a.x + b.x, a.y + b.y);
}

Vector operator - (Point a, Point b)
{
    return Vector(a.x - b.x, a.y - b.y);
}

int dcmp(double x)
{
    if(fabs(x) < eps)
        return 0;
    else return x < 0 ? -1 : 1;
}

bool operator == (const Point& a, Point& b){
    return !dcmp(a.x - b.x) && !dcmp(a.y - b.y);
}

double Dot(Point A, Point B)
{
    return A.x * B.x + A.y * B.y;
}

double Cross(Point A, Point B)
{
    return A.x * B.y - A.y * B.x;
}

bool on_segment(Point p, Point a, Point b)
{
    return dcmp(Cross(a - p, b - p)) == 0 && dcmp(Dot(a - p, b - p)) <= 0;
}

bool onSegment(Point Pi, Point Pj, Point Q)
{
    if((Q.x - Pi.x) * (Pj.y - Pi.y) == (Pj.x - Pi.x) * (Q.y - Pi.y)  //叉乘
       //保证Q点坐标在pi,pj之间
       && min(Pi.x , Pj.x) <= Q.x && Q.x <= max(Pi.x , Pj.x)
       && min(Pi.y , Pj.y) <= Q.y && Q.y <= max(Pi.y , Pj.y))
        return true;
    else
        return false;
}

double get_dist(Point a, Point b)
{
    double fa = a.x - b.x;
    double fb = a.y - b.y;
    return sqrt(fa * fa + fb * fb);
}

bool check(double x, double sin){
    double ans = bp * sin * (bc - x);//三角形面积,除以2之后还要乘以2
    return ans < area;
}

void solve()
{
    scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &a.x, &a.y, &b.x, &b.y, &c.x, &c.y, &p.x, &p.y);
    //if(on_segment(p, a, b))cout << "OK" << endl;
    if(!on_segment(p, a, b) && !on_segment(p, a, c) && !on_segment(p, b, c)){
        puts("-1");
        return ;
    }

    if(p == a){
        double fx = (b.x + c.x) / 2.0;
        double fy = (b.y + c.y) / 2.0;
        printf("%.10f %.10f\n", fx, fy);
        return ;
    }
    else if(p == b){
        double fx = (a.x + c.x) / 2.0;
        double fy = (a.y + c.y) / 2.0;
        printf("%.10f %.10f\n", fx, fy);
        return ;
    }
    else if(p == c){
        double fx = (a.x + b.x) / 2.0;
        double fy = (a.y + b.y) / 2.0;
        printf("%.10f %.10f\n", fx, fy);
        return ;
    }

    if(on_segment(p, a, b)){ }
    else if(on_segment(p, a, c))swap(b, c);
    else if(on_segment(p, b, c))swap(a, c);

    //统一让p点里a近一些
    if(get_dist(p, a) > get_dist(p, b))swap(a, b);


    ac = get_dist(a, c);
    ab = get_dist(a, b);
    bc = get_dist(b, c);
    ap = get_dist(a, p);
    bp = get_dist(b, p);
    //pc = get_dist(p, c);

    double k = (ab + ac + bc) / (double)2;
    area = sqrt(k * (k - ab) * (k - ac) * (k - bc));
    sina = area * 2 / ac / ab;
    sinb = area * 2 / ab / bc;
    sinc = area * 2 / ac / bc;

    double l = 0.0, r = bc;
    while(l + eps < r){
        double mid = (l + r) / (double)2;
        if(check(mid, sinb))r = mid;
        else l = mid;
    }

    double len = l;

    q.x = (b.x - c.x) * len / (bc) + c.x;
    q.y = (b.y - c.y) * len / (bc) + c.y;
    printf("%.10f %.10f\n", q.x, q.y);
    return ;
}


int main()
{
    scanf("%d", &t);
    while(t -- ){
        solve();
    }
    return 0;
}


本文链接: http://www.dtmao.cc/news_show_250322.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?