第七届蓝桥杯决赛试题：广场舞

时间：2022-04-11 16:42:41

题目:


广场舞

LQ市的市民广场是一个多边形，广场上铺满了大理石的地板砖。

地板砖铺得方方正正，就像坐标轴纸一样。
以某四块砖相接的点为原点，地板砖的两条边为两个正方向，一块砖的边长为横纵坐标的单位长度，则所有横纵坐标都为整数的点都是四块砖的交点（如果在广场内）。

广场的砖单调无趣，却给跳广场舞的市民们提供了绝佳的参照物。每天傍晚，都会有大批市民前来跳舞。
舞者每次都会选一块完整的砖来跳舞，两个人不会选择同一块砖，如果一块砖在广场边上导致缺角或者边不完整，则没人会选这块砖。
（广场形状的例子参考【图1.png】）

现在，告诉你广场的形状，请帮LQ市的市长计算一下，同一时刻最多有多少市民可以在广场跳舞。



【输入格式】
输入的第一行包含一个整数n，表示广场是n边形的（因此有n个顶点）。
接下来n行，每行两个整数，依次表示n边形每个顶点的坐标（也就是说广场边缘拐弯的地方都在砖的顶角上。数据保证广场是一个简单多边形。

【输出格式】
输出一个整数，表示最多有多少市民可以在广场跳舞。

【样例输入】
5
3 3
6 4
4 1
1 -1
0 4

【样例输出】
7

【样例说明】
广场如图1.png所示，一共有7块完整的地板砖，因此最多能有7位市民一起跳舞。

【数据规模与约定】
对于30%的数据，n不超过100，横纵坐标的绝对值均不超过100。
对于50%的数据，n不超过1000，横纵坐标的绝对值均不超过1000。
对于100%的数据，n不超过1000，横纵坐标的绝对值均不超过100000000（一亿）。


资源约定：
峰值内存消耗 < 256M
CPU消耗  < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意: main函数需要返回0
注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。
注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。

提交时，注意选择所期望的编译器类型。

第七届蓝桥杯决赛试题：广场舞

代码老实人的做法，仅供参考 

// 广场舞
#include <bits/stdc++.h>
using namespace std;

#define MX 100000001
#define MI -100000001

int n;
class Point {
public:     
    Point() = default;
    Point(long ix, long iy) : x(ix), y(iy) { }
    long x, y;

    bool operator == (const Point& p)
    {
        if(p.x==x && p.y==y) return true;
        return false;
    }

    bool operator < (const Point& p) const
    {
        if(p.x<x) return true;
        if(p.x==x&&p.y<y) return true;
        return false;
    } 
};

Point pn[1000];
set<Point> pset;

class Line {
public:
    Line(Point ip1, Point ip2) : p1(ip1), p2(ip2) { 
        kmom = p1.y-p2.y;
        kson = p1.x-p2.x;
        bson = kson;
        bmom = p1.y*kson-kmom*p1.x;
        left = min(p1.x,p2.x);
        right = max(p1.x,p2.x);
        top = max(p1.y,p2.y);
        bottom = min(p1.y,p2.y);
    }
    Line() = default;   
    Point p1, p2;
    long kmom, kson, bmom, bson, left, right, top, bottom;
};


class Square {
public:
    Square(long ileft, long iright, long itop, long ibottom) : left(ileft), right(iright), top(itop), bottom(ibottom) { 
        width = right-left;
        height = top-bottom;
        square = new Point*[top-bottom+1];
        for(int k=0;k<(top-bottom+1); ++k) {
            square[k] = new Point[right-left+1];
        }
        for(long y=top, i=0; y>=bottom; --y,++i) {
            for(long x=left,j=0; x<=right; ++x,++j) {
                square[i][j] = Point(x,y);
            }
        }
    }
    Square() = default;
    long left, right, top, bottom;
    Point **square;
    long width, height;
};

Square xsquare;
Point **square;

Line ln[1000];

void gline()
{
    for(int i=0; i<n; ++i) {
        Point p1 = pn[i];
        Point p2 = pn[(i+1)%n];
        ln[i] = Line(p1,p2);
    }
}

void init()
{
    cin >> n;
    long x, y, left=MX, right=MI, bottom=MX, top=MI;
    for(int i=0; i<n; ++i) {
        cin >> x >> y;
        pn[i] = Point(x,y);
        if(x>right) right = x;
        if(x<left) left = x;
        if(y>top) top = y;
        if(y<bottom) bottom = y;
    }
    gline();
    xsquare = Square(left,right,top,bottom);
    square = xsquare.square;
}

set<int> getIgnore(long y)
{
    set<int> tset;
    int topsum(0), bottomsum(0);
    for(int i=0; i<n; ++i) {
        if(ln[i].top==y) {
            tset.insert(i);
            topsum += 1;
        }
        if(ln[i].bottom==y) {
            tset.insert(i);
            bottomsum += 1;
        }
    }
    if(topsum==0||bottomsum==0) return tset;
    if(topsum==bottomsum){
        for(set<int>::iterator it = tset.begin(); it!=tset.end(); ++it,++it) {
            tset.erase(it);
        }
        return tset;
    }

}

bool isInSquare(Point p) 
{
    Point p1(p.x,p.y);
    for(int i=0; i<n; ++i) {
        if(p1==pn[i]) return true;  
    }

    double y = p.y*1.0, x = p.x*1.0;
    long sumleft(0), sumright(0);
    set<int> tset =  getIgnore(y);

    for(int i=0; i<n; ++i) {
        if(tset.find(i) != tset.end()) continue;
        Line xln = ln[i];
        double t = (xln.kmom*xln.bson*x + xln.bmom*xln.kson)/(xln.kson*xln.bson);
        if(y>xln.top*1.0||y<xln.bottom*1.0)  continue;

        if(y>t) {   
            if(xln.kmom*1.0/xln.kson*1.0<0) {
                sumleft += 1;
            } else if(xln.kmom*1.0/xln.kson*1.0>0) {
                sumright += 1;
            }

        } 
        if(y<t) {
            if(xln.kmom*1.0/xln.kson*1.0<0) {
                sumright += 1;  
            } else if(xln.kmom*1.0/xln.kson*1.0>0) {
                sumleft += 1;
            }
        }

    }
    if(sumleft%2 && sumright%2) return true;
    return false;   
}


void test_square()
{
    for(int i=0; i<=xsquare.height; ++i) {
        for(int j=0; j<=xsquare.width; ++j) {

            if(isInSquare(square[i][j])) {
                Point p = square[i][j];
                pset.insert(p);
            }

        }
    }
}

bool xjudge(Point p)
{
    if(pset.find(p)!=pset.end()) return true;
    return false;
}

long res(0);

long doit()
{
    for(long i=0; i<xsquare.height; ++i) {
        for(long j=0; j<xsquare.width; ++j) {
            if(xjudge(square[i][j])&&xjudge(square[i][j+1])&&
                xjudge(square[i+1][j])&&xjudge(square[i+1][j+1])) {
                res += 1;       
            }
        }
    }
    return res;
}

int main()
{
    init();
    test_square();  
    cout << doit() << endl;

    return 0;
}
标签：

相关文章