Codeforeces 13B-Letter A

二维基础

题目链接：https://codeforces.com/problemset/problem/13/B

题意：给定三条线段，判断三条线段是否是“A”形的。“A”形的定义如下：

线段A和线段B有一个公共点。
线段C的两个端点分别位于线段A和线段B上。
线段A和线段B所形成的夹角在\((0^\circ,90^\circ]\)。
线段C分线段A为\(x_1\)和\(x_2\)两部分且较短线段与较长线段的比值大于等于\(1/4\)，线段B亦是。

思路：这是一道十分基础的练习题。只需要读取输入后按照条件一项一项判断即可。对于每一个条件，我们可以这样判断：

在给定的6个端点中有且仅有2个点的坐标一致。
设线段A的两个端点为\(a_1和a_2\)且线段C的端点\(c_1\)在线段A上，则有\(\vec {c_1a_1} \times \vec{c_1a_2} = 0\) 并且 \(\vec {c_1a_1} \cdot \vec{c_1a_2} < 0\)，线段B同理。
设线段A和线段B的公共点为\(x_1\)，各自另外一点分别为\(a_1,b_1\)，则有\(\vec {x_1a_1} \cdot \vec{x_1b_1} \geq 0\) 并且 \(\vec {x_1a_1} \times \vec{x_1b_1} \neq 0\)。
设线段A的两个端点为\(a_1和a_2\)且线段C的端点\(c_1\)在线段A上，则有\(16*min(\vert \vec {c_1a_1}\vert^2,\vert \vec {c_1a_2}\vert^2) \geq max(\vert \vec {c_1a_1}\vert^2,\vert \vec {c_1a_2}\vert^2)\)，线段B同理。
*此处使用线段长度的平方判断，避免开根号带来的精度误差。

代码如下:

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

#define ywh666 std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

#define all(a) a.begin(),a.end()

typedef long long ll ;

using _T = long long;//long long

const _T eps = 0;// 0

template<typename T> struct point

{

    T x,y;

    void read(){cin >> x >> y;}

    bool operator<(const point &a) const

    {if (abs(x-a.x)<=eps) return y<a.y-eps; return x<a.x-eps;}

    bool operator>(const point &a) const

    {return !(*this<a || *this==a);}

    bool operator==(const point &a) const

    {return (abs(x-a.x)<=eps && abs(y-a.y)<=eps);}

    bool operator!=(const point &a) const

    {return (abs(x-a.x)>eps || abs(y-a.y)>eps);}

    point operator+(const point &a) const {return {x+a.x,y+a.y};}

    point operator-(const point &a) const {return {x-a.x,y-a.y};}

    point operator-() const {return {-x,-y};}

    point operator*(const T k) const {return {k*x,k*y};}

    point operator/(const T k) const {return {x/k,y/k};}

    T operator*(const point &a) const {return x*a.x+y*a.y;}

    T operator^(const point &a) const {return x*a.y-y*a.x;}

        T dis2(const point &a) const {return (a-(*this)).len2();}

        T len2() const {return (*this)*(*this);}

};

using Point = point<_T>;

map<Point, int> mp;

bool check(Point bo, Point end1, Point end2, Point a1, Point a2){

    if(((end1 - bo) ^ (end2 - bo)) == 0) return 0 ;

    if(((end1 - bo) * (end2 - bo)) < 0) return 0 ;

    if(((end1 - a1) ^ (bo - a1)) == 0 &&((end1 - a1) * (bo - a1) < 0)

       && ((end2 - a2) ^ (bo - a2)) == 0 &&((end2 - a2) * (bo - a2) < 0)){

        if(16 * min(bo.dis2(a1), a1.dis2(end1)) >= max(bo.dis2(a1), a1.dis2(end1)) &&

           16 * min(bo.dis2(a2), a2.dis2(end2)) >= max(bo.dis2(a2), a2.dis2(end2))){

            return 1 ;

        }else{

            return 0 ;

        }

    }else if(((end1 - a2) ^ (bo - a2)) == 0 &&((end1 - a2) * (bo - a2) < 0)

       && ((end2 - a1) ^ (bo - a1)) == 0 &&((end2 - a1) * (bo - a1) < 0)){

        if(16 * min(bo.dis2(a2), a2.dis2(end1)) >= max(bo.dis2(a2), a2.dis2(end1)) &&

           16 * min(bo.dis2(a1), a1.dis2(end2)) >= max(bo.dis2(a1), a1.dis2(end2))){

            return 1 ;

        }else{

            return 0 ;

        }

    }else{

        return 0 ;

    }

}

void solve(){

    Point a[6];

    mp.clear();

        for(int i = 0 ; i < 6 ; i ++) {

            a[i].read();

            mp[a[i]] ++;

        }

        bool f = 0 ;

        Point both;

        for(auto i : mp){

            if(i.second == 2 && !f){

                both = i.first;

                f = 1;

            }else if(i.second != 1){

                cout << "NO" << endl;

                return ;

            }

        }

        if(!f){

            cout << "NO" << endl;

            return ;

        }

        mp.clear();

        Point cnt[4];

        int nn = 0 ;

        for(int i = 0 ; i < 6 ; i ++){

            if(a[i] == both){

                cnt[nn ++] = a[(((i & 1) == 1) ? (i - 1) : (i + 1))];

                mp[cnt[nn - 1]] ++;

            }

        }

        for(int i = 0 ; i < 6 ; i ++){

            if(!mp.count(a[i]) && a[i] != both) cnt[nn ++] = a[i];

        }

        bool ff = check(both, cnt[0], cnt[1], cnt[2], cnt[3]);

        if(ff){

            cout << "YES" << endl;

        }else{

            cout << "NO" << endl;

        }

        return ;

}

int main(){

    ywh666;

    int t ;

    cin >> t;

    while(t --){

        solve();

    }

    return 0 ;

}

巴特西

Codeforeces 13B

Codeforeces 13B-Letter A

二维基础

题目链接：https://codeforces.com/problemset/problem/13/B

题意：给定三条线段，判断三条线段是否是“A”形的。“A”形的定义如下：

思路：这是一道十分基础的练习题。只需要读取输入后按照条件一项一项判断即可。对于每一个条件，我们可以这样判断：

代码如下:

最新文章

热门文章