论坛 › C\C++交流 › 美丽几何

727181660 发表于 2020-12-23 10:57:37

美丽几何

本帖最后由 727181660 于 2020-12-26 19:42 编辑

在平面上有n个点，初始每个点的美丽值都为0，任意选择两个点组成一条
直线，对于每一条直线，如果存在一个点，这个点到这条直线的距离小于其他
n-3个点到这条直线的距离，那么我们把这个点的美丽值加1。为了简化输出，
我们只需要输出所有点的美丽值的异或值，保证三点不共线。
输入说明
第一行一个正整数n(4<=n<=2000)
接下来n行，每一行有2个正整数x,y。代表一个点的坐标(0<=x,y<=100000000)
输出说明
输出所有点的美丽值的异或值。
输入样例
4
00
01
10
11
4
00
10
12
21
输出样例
0
3

727181660 发表于 2020-12-23 11:17:41

求救求救！

心驰神往 发表于 2020-12-23 11:50:55

等大佬吧

727181660 发表于 2020-12-23 15:51:40

来人啊

727181660 发表于 2020-12-23 17:23:03

大哥大姐们救救孩子吧

727181660 发表于 2020-12-24 00:25:59

来个大佬救救我呀

玛了个巴卡 发表于 2020-12-24 13:17:40

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
typedef pair<int,int> PII;
const int N=2005;
int n,ml,res;
double A,B,C;
PII pa;
bool b;

void line(PII a,PII b){
        if(a.first==b.first){
                A=1,B=0,C=-a.first;
                return;
        }
        A=(b.second-a.second)/(b.first-a.first);
        C=a.second-A*a.first;
        A=-A,C=-C,B=1;
}

inline double distance(PII a){
        return fabs(A*a.first+B*a.second+C)/sqrt(A*A+B*B);
}

int func(){
        double dis;
        bool is_min=true;
        for(int i=0;i<n;i++){
                b=true;
                for(int j=i+1;j<n;j++){
                        b=true;
                        line(pa,pa);
                        for(int m=0;m<n;m++){
                                if(!b){
                                        b=true;
                                        is_min=true;
                                        dis=distance(pa);
                                        for(int k=0;k<n;k++){
                                                if(!b&&distance(pa)<=dis){
                                                        is_min=false;
                                                        break;
                                                }
                                        }
                                        if(is_min)
                                                ml++;
                                        b=false;
                                }
                        }
                        b=false;
                }
                b=false;
        }
}
int main(){
        int a,b;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
                scanf("%d%d",&a,&b);
                pa={a,b};
        }
        func();
        for(int i=0;i<n;i++)
                res^=ml;
        printf("%d",res);
}

727181660 发表于 2020-12-26 19:41:56

求根据大神的解题给出解题思路解法

727181660 发表于 2020-12-26 19:49:31

玛了个巴卡 发表于 2020-12-24 13:17


大哥能不能给一些解题思路

查看完整版本: 美丽几何