提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

2020安徽程序设计省赛 I美丽几何

2023-04-18 12:35:30 时间

2020安徽程序设计省赛 I美丽几何

在平面上有n 个点，初始每个点的美丽值都为0，任意选择两个点组成一条直线，对于每一条直线，如果存在一个点，这个点到这条直线的距离小于其他n-3 个点到这条直线的距离，那么我们把这个点的美丽值加1。为了简化输出，我们只需要输出所有点的美丽值的异或值，保证三点不共线。

解题思路

据美丽值的定义：对于每一条直线，如果存在一个点，这个点到这条直线的距离小于其他点到这条直线的距离，那么我们把这个点的美丽值加1。求解所有的点的美丽值，即对于每一条直线，寻找距离其最近的一个点(若有多个点到直线距离相同则全部不计)。 想要完成上述过程，最朴素的思想是，先用O(n^2)的时间复杂度枚举出所有的直线，然后再用O(n)的时间复杂度枚举每个点到直线的距离，最后求出所有点的美丽值并输出异或的结果。这样的算法时间复杂度恒为O ( n 3 ) O(n^3)O(n 3)

#include <iostream>
#include <ostream>
#include <vector>
#include <cmath>

using namespace std;

class Point {
private:
    int x, y, beauty = 0;
public:
    Point(int a, int b)
    {
        x = a;
        y = b;
    }
    int getX() { return x; }
    int getY() { return y; }
    int getBeauty() { return beauty; }
    void addBeauty() { beauty++; }
    bool operator==(Point a)
    {
        if (a.x != this->x)
        {
            return false;
        }
        else if(a.y != this->y)
        {
            return false;
        }
        return true;
    }
};
    

class Line {
private:
    Point p1, p2;
public:
    Line(const Point& _p1, const Point& _p2):p1(_p1), p2(_p2)
    {
        p1 = _p1;
        p2 = _p2;
    }

    friend double distance(Line &p, Point &q)
    {
        double x1 = p.p1.getX(), y1 = p.p1.getY();
        double x2 = p.p2.getX(), y2 = p.p2.getY();
        double x = q.getX(), y = q.getY();
        double distance = 0.0;
        distance = ((x-x1)*(y2-y1)-(x2-x1)*(y-y1))/sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
        return abs(distance);
    }

    friend ostream& operator<<(ostream& out, Line& l)
    {
        out << "A: (" << l.p1.getX() << "," << l.p1.getY() << "), "
            << "B: (" << l.p2.getX() << "," << l.p2.getY() << ")" << endl;
        return out;
    }

    Point getPoint1() { return p1; }
    Point getPoint2() { return p2; }
};

vector<Line> getLines(vector<Point>& points)
{
    vector<Line> lines;
    int size = points.size();
    for(size_t i = 0; i < size; i++)
    {
        for(size_t j = i + 1; j < size; j++)
        {
            Line line(points[i], points[j]);
            lines.push_back(line);
        }
    }

    return lines;
}


void computeBeauty(vector<Line>& lines, vector<Point>& points)
{
    for(int i = 0; i < lines.size(); i++)
    {
    	bool beauty = true, flag = false;
    	int minIndex = 0;
        double min;
        for(int j = 0; j < points.size(); j++)
        {
            if (points[j] == lines[i].getPoint1() || points[j] == lines[i].getPoint2())
            {
                continue;
            }
            double dis = distance(lines[i], points[j]);
            if(!flag)
            {
                min = dis;
                minIndex = j;
                flag = true;
            }
            else if (dis < min)
            {
                min = dis;
                minIndex = j;
            } else if (dis == min)
            {
            	beauty = false;
            	break;
			}
        }
        if(beauty && flag)
        {
        	points[minIndex].addBeauty();
		}
    }
}

int main()
{
   	int n, x, y, result = 0;
    vector<Point> points;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
    	cin >> x >> y;
    	Point p(x, y);
    	points.push_back(p);
	}
    vector<Line> lines = getLines(points);

//    for(size_t i = 0; i < lines.size(); i++)
//    {
//        cout << "line " << i+1 << ": " << lines[i];
//    }
    computeBeauty(lines, points);
    result = points[0].getBeauty();
    //cout << "beauty 0 = " << result << endl;
    int i = 1;
    for(auto it = points.begin() + 1; it != points.end(); it++)
    {
    	//cout << "beauty " << i << " = " << it->getBeauty() << endl;
        result ^= it->getBeauty();
        i++;
    }
    
    cout << result << endl;
    return 0;
}

相关文章