[已解决]美丽几何

727181660

在平面上有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

最佳答案

月排行榜 / 总排行榜

玛了个巴卡

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[N],res;
double A,B,C;
PII pa[N];
bool b[N];

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[i]=true;
                for(int j=i+1;j<n;j++){
                        b[j]=true;
                        line(pa[i],pa[j]);
                        for(int m=0;m<n;m++){
                                if(!b[m]){
                                        b[m]=true;
                                        is_min=true;
                                        dis=distance(pa[m]);
                                        for(int k=0;k<n;k++){
                                                if(!b[k]&&distance(pa[k])<=dis){
                                                        is_min=false;
                                                        break;
                                                }
                                        }
                                        if(is_min)
                                                ml[m]++;
                                        b[m]=false;
                                }
                        }
                        b[j]=false;
                }
                b[i]=false;
        }
}
int main(){
        int a,b;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
                scanf("%d%d",&a,&b);
                pa[i]={a,b};
        }
        func();
        for(int i=0;i<n;i++)
                res^=ml[i];
        printf("%d",res);
}

跳转到最佳答案楼层

727181660

求救求救！

心驰神往

等大佬吧

727181660

来人啊

727181660

大哥大姐们救救孩子吧

727181660

来个大佬救救我呀

玛了个巴卡

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

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[i]=true;
                for(int j=i+1;j<n;j++){
                        b[j]=true;
                        line(pa[i],pa[j]);
                        for(int m=0;m<n;m++){
                                if(!b[m]){
                                        b[m]=true;
                                        is_min=true;
                                        dis=distance(pa[m]);
                                        for(int k=0;k<n;k++){
                                                if(!b[k]&&distance(pa[k])<=dis){
                                                        is_min=false;
                                                        break;
                                                }
                                        }
                                        if(is_min)
                                                ml[m]++;
                                        b[m]=false;
                                }
                        }
                        b[j]=false;
                }
                b[i]=false;
        }
}
int main(){
        int a,b;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
                scanf("%d%d",&a,&b);
                pa[i]={a,b};
        }
        func();
        for(int i=0;i<n;i++)
                res^=ml[i];
        printf("%d",res);
}

727181660

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

727181660

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

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