[已解决]美丽几何

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

1. #include <cstdio>
   
2. #include <vector>
   
3. #include <cmath>
   
4. using namespace std;
   
5. typedef pair<int,int> PII;
   
6. const int N=2005;
   
7. int n,ml[N],res;
   
8. double A,B,C;
   
9. PII pa[N];
   
10. bool b[N];
    
11. 
    
12. void line(PII a,PII b){
    
13.         if(a.first==b.first){
    
14.                 A=1,B=0,C=-a.first;
    
15.                 return;
    
16.         }
    
17.         A=(b.second-a.second)/(b.first-a.first);
    
18.         C=a.second-A*a.first;
    
19.         A=-A,C=-C,B=1;
    
20. }
    
21. 
    
22. inline double distance(PII a){
    
23.         return fabs(A*a.first+B*a.second+C)/sqrt(A*A+B*B);
    
24. }
    
25. 
    
26. int func(){
    
27.         double dis;
    
28.         bool is_min=true;
    
29.         for(int i=0;i<n;i++){
    
30.                 b[i]=true;
    
31.                 for(int j=i+1;j<n;j++){
    
32.                         b[j]=true;
    
33.                         line(pa[i],pa[j]);
    
34.                         for(int m=0;m<n;m++){
    
35.                                 if(!b[m]){
    
36.                                         b[m]=true;
    
37.                                         is_min=true;
    
38.                                         dis=distance(pa[m]);
    
39.                                         for(int k=0;k<n;k++){
    
40.                                                 if(!b[k]&&distance(pa[k])<=dis){
    
41.                                                         is_min=false;
    
42.                                                         break;
    
43.                                                 }
    
44.                                         }
    
45.                                         if(is_min)
    
46.                                                 ml[m]++;
    
47.                                         b[m]=false;
    
48.                                 }
    
49.                         }
    
50.                         b[j]=false;
    
51.                 }
    
52.                 b[i]=false;
    
53.         }
    
54. }
    
55. int main(){
    
56.         int a,b;
    
57.         scanf("%d",&n);
    
58.         for(int i=0;i<n;i++){
    
59.                 scanf("%d%d",&a,&b);
    
60.                 pa[i]={a,b};
    
61.         }
    
62.         func();
    
63.         for(int i=0;i<n;i++)
    
64.                 res^=ml[i];
    
65.         printf("%d",res);
    
66. }

复制代码

跳转到最佳答案楼层

727181660

求救求救！

心驰神往

等大佬吧

727181660

来人啊

727181660

大哥大姐们救救孩子吧

727181660

来个大佬救救我呀

玛了个巴卡

1. #include <cstdio>
   
2. #include <vector>
   
3. #include <cmath>
   
4. using namespace std;
   
5. typedef pair<int,int> PII;
   
6. const int N=2005;
   
7. int n,ml[N],res;
   
8. double A,B,C;
   
9. PII pa[N];
   
10. bool b[N];
    
11. 
    
12. void line(PII a,PII b){
    
13.         if(a.first==b.first){
    
14.                 A=1,B=0,C=-a.first;
    
15.                 return;
    
16.         }
    
17.         A=(b.second-a.second)/(b.first-a.first);
    
18.         C=a.second-A*a.first;
    
19.         A=-A,C=-C,B=1;
    
20. }
    
21. 
    
22. inline double distance(PII a){
    
23.         return fabs(A*a.first+B*a.second+C)/sqrt(A*A+B*B);
    
24. }
    
25. 
    
26. int func(){
    
27.         double dis;
    
28.         bool is_min=true;
    
29.         for(int i=0;i<n;i++){
    
30.                 b[i]=true;
    
31.                 for(int j=i+1;j<n;j++){
    
32.                         b[j]=true;
    
33.                         line(pa[i],pa[j]);
    
34.                         for(int m=0;m<n;m++){
    
35.                                 if(!b[m]){
    
36.                                         b[m]=true;
    
37.                                         is_min=true;
    
38.                                         dis=distance(pa[m]);
    
39.                                         for(int k=0;k<n;k++){
    
40.                                                 if(!b[k]&&distance(pa[k])<=dis){
    
41.                                                         is_min=false;
    
42.                                                         break;
    
43.                                                 }
    
44.                                         }
    
45.                                         if(is_min)
    
46.                                                 ml[m]++;
    
47.                                         b[m]=false;
    
48.                                 }
    
49.                         }
    
50.                         b[j]=false;
    
51.                 }
    
52.                 b[i]=false;
    
53.         }
    
54. }
    
55. int main(){
    
56.         int a,b;
    
57.         scanf("%d",&n);
    
58.         for(int i=0;i<n;i++){
    
59.                 scanf("%d%d",&a,&b);
    
60.                 pa[i]={a,b};
    
61.         }
    
62.         func();
    
63.         for(int i=0;i<n;i++)
    
64.                 res^=ml[i];
    
65.         printf("%d",res);
    
66. }

复制代码

727181660

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

727181660

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

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