列表

详情

NC233985. Mogohu-Rea Idol

描述

A long time ago somewhere in the depths of America existed a powerful tribe governed by the great leader Pinnie-the-Wooh. Once the tribe conquered three Maya cities. Pinnie-the-Wooh grew concerned: there had to be some control over the conquered territories. That's why he appealed to the priests of the supreme god Mogohu-Rea for help.

The priests conveyed the god's will to him: to control these three cities he should put an idol to Mogohu-Rea — that will create a religious field over the cities. However, the idol is so powerful that it can easily drive the people around it mad unless it is balanced by exactly three sacrifice altars, placed one in each city. To balance the idol the altars should be placed so that the center of mass of the system of these three points coincided with the idol. When counting the center of mass consider that all the altars have the same mass.

Now Pinnie-the-Wooh is thinking where to put the idol. He has a list of hills, that are suitable to put an idol there. Help him to identify on which of them you can put an idol without risking to fry off the brains of the cities' population with the religious field.

Each city has a shape of a convex polygon such that no three vertexes lie on a straight line. The cities can intersect. Each altar should be attached to the city through a special ceremony, besides, it must be situated on the city's territory (possibly at the border). Thus, there may be several altars on a city's territory, but exactly one of them will be attached to the city. The altars, the idol and the hills are points on the plane, some of them may coincide.

The hills are taken into consideration independently from each other, the altars' location for different hills may also be different.

输入描述

First follow descriptions of the three cities, divided by empty lines. The descriptions are in the following format:

The first line contains an integer n, which represent the number of the polygon's vertexes . Next n lines contain two integers x_i, y_i each, they are the coordinates of the polygon's i-th vertex in the counterclockwise order.

After the cities' description follows the integer m , which represents the number of hills. Next m lines each contain two integers x_j, y_j, they are the coordinates of the j-th hill.

All the coordinates in the input data do not exceed  in the absolute value.

输出描述

For each hill print on a single line "YES" (without the quotes) or "NO" (without the quotes), depending on whether the three sacrifice altars can be put to balance the idol or not.

示例1

输入: 

3
0 0
1 0
1 1

4
8 8
5 5
6 4
8 4

3
-1 -1
-3 -1
-2 -2

5
0 0
2 1
7 1
1 1
5 3

输出: 

NO
YES
NO
YES
NO

说明:

For the hill at (2, 1) the altars can be placed at the points (1, 0), (7, 5), (-2, -2), for the hill at (1, 1) — at the points (0, 0), (6, 4), ( -3, -1). Many other groups of three points can do the trick. There are no suitable points for other hills.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 133ms, 内存消耗: 18512K, 提交时间: 2023-02-18 10:45:49 

#include <bits/stdc++.h>
using namespace std;
 
using point_t=long long ;  //全局数据类型，可修改为 long long 等
 
constexpr point_t eps=1e-8;
constexpr long double PI=3.1415926535897932384l;
 
// 点与向量
template<typename T> struct point
{
    T x,y;
 
    bool operator==(const point &a) const {return (abs(x-a.x)<=eps && abs(y-a.y)<=eps);}
    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);}
    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;}  // 叉积，注意优先级
    int toleft(const point &a) const {const auto t=(*this)^a; return (t>eps)-(t<-eps);}  // to-left 测试，>0 左侧，=0 直线上，<0 右侧
    T len2() const {return (*this)*(*this);}  // 向量长度的平方
    T dis2(const point &a) const {return (a-(*this)).len2();}  // 两点距离的平方
 
    // 涉及浮点数
    long double len() const {return sqrtl(len2());}  // 向量长度
    long double dis(const point &a) const {return sqrtl(dis2(a));}  // 两点距离
    long double ang(const point &a) const {return acosl(max(-1.0l,min(1.0l,((*this)*a)/(len()*a.len()))));}  // 向量夹角
    point rot(const long double rad) const {return {x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad)};}  // 逆时针旋转（给定角度）
    point rot(const long double cosr,const long double sinr) const {return {x*cosr-y*sinr,x*sinr+y*cosr};}  // 逆时针旋转（给定角度的正弦与余弦）
};
 
using Point=point<point_t>;

// 极角排序
struct argcmp
{
    bool operator()(const Point &a,const Point &b) const
    {
        const auto quad=[](const Point &a)
        {
            if (a.y<-eps) return 1;
            if (a.y>eps) return 4;
            if (a.x<-eps) return 5;
            if (a.x>eps) return 3;
            return 2;
        };
        const int qa=quad(a),qb=quad(b);
        if (qa!=qb) return qa<qb;
        const auto t=a^b;
        // if (abs(t)<=eps) return a*a<b*b-eps;  // 不同长度的向量需要分开
        return t>eps;
    }
};
// 直线
template<typename T> struct line
{
    point<T> p,v;  // p 为直线上一点，v 为方向向量
 
    bool operator==(const line &a) const {return v.toleft(a.v)==0 && v.toleft(p-a.p)==0;}
    int toleft(const point<T> &a) const {return v.toleft(a-p);}  // to-left 测试
 
    // 涉及浮点数
};

using Line=line<point_t>;
//线段
template<typename T> struct segment
{
    point<T> a,b;
 
    // 判定性函数建议在整数域使用
 
    // 判断点是否在线段上
    // -1 点在线段端点 | 0 点不在线段上 | 1 点严格在线段上
    int is_on(const point<T> &p) const 
    {
        if (p==a || p==b) return -1;
        return (p-a).toleft(p-b)==0 && (p-a)*(p-b)<-eps;
    }
};
 
using Segment=segment<point_t>;
//凸多边形
template<typename T> struct convex
{
    vector<point<T>> p;  // 以逆时针顺序存储
 
    size_t nxt(const size_t i) const {return i==p.size()-1?0:i+1;}
    size_t pre(const size_t i) const {return i==0?p.size()-1:i-1;}
     // 多边形面积的两倍
    // 可用于判断点的存储顺序是顺时针或逆时针
    T area() const
    {
        T sum=0;
        for (size_t i=0;i<p.size();i++) sum+=p[i]^p[nxt(i)];
        return sum;
    }
    // 闵可夫斯基和
    convex operator+(const convex &c) const 
    {
        const auto &p=this->p;
        vector<Segment> e1(p.size()),e2(c.p.size()),edge(p.size()+c.p.size());
        vector<point<T>> res; res.reserve(p.size()+c.p.size());
        const auto cmp=[](const Segment &u,const Segment &v) {return argcmp()(u.b-u.a,v.b-v.a);};
        for (size_t i=0;i<p.size();i++) e1[i]={p[i],p[this->nxt(i)]};
        for (size_t i=0;i<c.p.size();i++) e2[i]={c.p[i],c.p[c.nxt(i)]};
        rotate(e1.begin(),min_element(e1.begin(),e1.end(),cmp),e1.end());
        rotate(e2.begin(),min_element(e2.begin(),e2.end(),cmp),e2.end());
        merge(e1.begin(),e1.end(),e2.begin(),e2.end(),edge.begin(),cmp);
        // 删除三点共线情况(check)
        const auto check=[](const vector<point<T>> &res,const point<T> &u)
        {
            const auto back1=res.back(),back2=*prev(res.end(),2);
            return (back1-back2).toleft(u-back1)==0 && (back1-back2)*(u-back1)>=-eps;
        };
        auto u=e1[0].a+e2[0].a;
        for (const auto &v:edge)
        {
            while (res.size()>1 && check(res,u)) res.pop_back();
            res.push_back(u);
            u=u+v.b-v.a;
        }
        if (res.size()>1 && check(res,res[0])) res.pop_back();
        return {res};
    }
    // 判断点是否在凸多边形内
    // 复杂度 O(logn)
    // -1 点在多边形边上 | 0 点在多边形外 | 1 点在多边形内
    int is_in(const point<T> &a) const
    {
        const auto &p=this->p;
        if (p.size()==1) return a==p[0]?-1:0;
        if (p.size()==2) return segment<T>{p[0],p[1]}.is_on(a)?-1:0;
        if (a==p[0]) return -1;
        if ((p[1]-p[0]).toleft(a-p[0])==-1 || (p.back()-p[0]).toleft(a-p[0])==1) return 0;
        const auto cmp=[&](const Point &u,const Point &v){return (u-p[0]).toleft(v-p[0])==1;};
        const size_t i=lower_bound(p.begin()+1,p.end(),a,cmp)-p.begin();
        if (i==1) return segment<T>{p[0],p[i]}.is_on(a)?-1:0;
        if (i==p.size()-1 && segment<T>{p[0],p[i]}.is_on(a)) return -1;
        if (segment<T>{p[i-1],p[i]}.is_on(a)) return -1;
        return (p[i]-p[i-1]).toleft(a-p[i-1])>0;
    }
};
 
using Convex=convex<point_t>;
#define ll long long

void solve()
{
    int k=3,n[3] ;
    Convex poly[3] ;
    for(int i=0;i<k;++i)
    {
        scanf("%d",&n[i]) ;
        for(int j=0,x,y;j<n[i];j++)
        {
            scanf("%d%d",&x,&y) ;
            poly[i].p.push_back(Point{x,y}) ;
        }
    }
    Convex nowpoly = poly[0] + poly[1] + poly[2] ;
    int m ; scanf("%d",&m) ;
    while(m--)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        printf("%s\n",nowpoly.is_in(Point{3*x, 3*y}) ? "YES" : "NO") ;
    }
}
int main()
{
    int T=1 ; //scanf("%d",&T) ;
    while(T--) solve() ;
    return 0 ;
}

C++(g++ 7.5.0) 解法, 执行用时: 124ms, 内存消耗: 10252K, 提交时间: 2022-09-02 00:54:23 

#include<bits/stdc++.h>
using namespace std;
#define ll long long

using _T = ll;
const _T eps = 0;

template<typename T> struct tpoint
{
    T x,y;
    tpoint(T x, T y):x(x),y(y){};
    tpoint(){};
    bool operator == (const tpoint &p) const { return x==p.x && y==p.y; }
    bool operator < (const tpoint &p) const { if(x==p.x)return y<p.y; return x<p.x; }
    tpoint operator + (const tpoint &p) const { return tpoint(x+p.x,y+p.y); }
    tpoint operator - (const tpoint &p) const { return tpoint(x-p.x,y-p.y); }
    T operator * (const tpoint &p) const { return x*p.x+y*p.y; }
    T operator ^ (const tpoint &p) const { return x*p.y-p.x*y; }
    int toleft(const tpoint &p) const { auto t=(*this)^p; return (t>0)-(t<0); }
    //void show() { printf("point: %lld %lld\n",x,y); }
};
using point = tpoint<_T>;
point p,p1,p2,pm;
vector<point> con[4],c,convexs;
ll n[4],totn;
ll minkvsk()
{
    ll i,arr[4],minnum,ok,sz=0,totsz=0;
    arr[1] = arr[2] = arr[3] = 1;
    c.resize(n[1]+n[2]+n[3]+5);
    convexs.resize(n[1]+n[2]+n[3]+5);
    c[++sz] = p;
    while(true)
    {
        ok = 3;
        for(i=1;i<=3;i++) if(arr[i] > n[i]) ok --;
        if(!ok) break;
        pm = point(0,0);
        for(i=1;i<=3;i++)
        {
            //con[i][arr[i]].show();
            if(arr[i] <= n[i] && pm.toleft(con[i][arr[i]]) <= 0)
            {
                minnum = i;
                pm = con[i][arr[i]];
            }
        }
        p = p + con[minnum][arr[minnum]];
        c[++sz] = p;
        arr[minnum] ++;
        //printf("now: %lld %lld\n",arr[minnum],minnum);
    }
    for(i=1;i<=sz;i++)
    {
        //c[i].show();
        if(i==1 || i==sz || (c[i]-c[i-1]).toleft(c[i]-c[i+1]) != 0)
            convexs[++totsz] = c[i];
    }
    return totsz-1;
}

bool pinconvex(point p)
{
    ll st = 2, en = totn-1, half,x,y;
    point p0 = convexs[1];
    while(en >= st)
    {
        half = en + (st - en) / 2;
        //printf("nowp:\n");
        //convexs[half].show(); convexs[half+1].show(); p.show();
        x = (convexs[half]-p0).toleft(p-p0);
        y = (convexs[half+1]-p0).toleft(p-p0);
        if(x >= 0 && y <= 0)
        {
            //printf("yes!\n");
            if((convexs[half+1]-convexs[half]).toleft(p-convexs[half]) >= 0) return 1;
            return 0;
        }
        else if(x >= 0 && st != en) st = half;
        else en = half - 1;
    }
    return 0;
}

int main()
{
    ll i,j,minpind,q;
    p = point(0,0);
    for(i=1;i<=3;i++)
    {
        scanf("%lld",&n[i]);
        con[i].resize(2*n[i]+2);
        minpind = 1;
        for(j=1;j<=n[i];j++)
        {
            scanf("%lld%lld",&con[i][j].x,&con[i][j].y);
            con[i][j+n[i]] = con[i][j];
            if(con[i][j] < con[i][minpind]) minpind = j;
        }
        for(j=1;j<=n[i];j++) con[i][j] = con[i][minpind+j-1];
        con[i][n[i]+1] = con[i][1];
        p = p + con[i][1];
        for(j=1;j<=n[i];j++) con[i][j] = con[i][j+1]-con[i][j];
    }
    totn = minkvsk();
    //printf("ok!\n");
    //for(i=1;i<=totn;i++) convexs[i].show();
    scanf("%lld",&q);
    while(q--)
    {
        scanf("%lld%lld",&p.x,&p.y);
        p.x = 3*p.x; p.y = 3*p.y;
        if(pinconvex(p)) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}
/*
3
0 0
1 0
1 1
4
8 8
5 5
6 4
8 4
3
-1 -1
-3 -1
-2 -2
10
0 0
2 1
7 1
1 1
5 3
3 3
*/

上一题

© 2024 nowcoder.com