超级传输 (Hypertransmission,NEERC 2003,LA 2963)

 1 #include <iostream>
 2 #include <string.h>
 3 #include <string>
 4 #include <fstream>
 5 #include <algorithm>
 6 #include <stdio.h>
 7 #include <vector>
 8 #include <queue>
 9 #include <set>
10 #include <cmath>
11 using namespace std;
12 const double eps = 1e-8;
13 #define MAXN 1001
14 struct node
15 {
16     int x,y,z,p;
17 }star[MAXN];
18 int Distance(node a,node b)
19 {
20     return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
21 }
22 struct node1
23 {
24     int a,b;
25     int dist;
26 }dis[MAXN*MAXN];
27 bool cmp(node1 a,node1 b)
28 {
29     return a.dist<b.dist;
30 }
31 int minr;
32 int num,numd;
33 int N[MAXN][2];
34 int main()
35 {
36     int n;
37     while(scanf("%d",&n)!=EOF)
38     {
39         memset(dis,0,sizeof(dis));numd=0;
40         for(int i=0;i<n;i++)
41         {
42         scanf("%d%d%d%d",&star[i].x,&star[i].y,&star[i].z,&star[i].p);
43         for(int j=0;j<i;j++)
44         if(i!=j)
45         {dis[numd].a=i;dis[numd].b=j;dis[numd++].dist=Distance(star[i],star[j]);
46             }
47         }
48         num=0;minr=0;
49         memset(N,0,sizeof(N));
50         sort(dis,dis+numd,cmp);
51         for(int i=0;i<numd;i++)
52         {
53             int temp=dis[i].dist;
54             while(dis[i].dist==temp){
55             N[dis[i].a][star[dis[i].b].p]++;
56             N[dis[i].b][star[dis[i].a].p]++;
57             i++;}
58             i--;
59             temp=0;
60             for(int j=0;j<n;j++)
61             {
62             if(N[j][star[j].p]+1<N[j][star[j].p^1])temp++;
63             }
64             if(temp>num){num=temp;minr=dis[i].dist;}
65         }
66         printf("%d
%.4lf
",num,sqrt(minr*1.0));
67     }
68     return 0;
69 }

View Code

poj 上没过，LA上过了继续优化~

 1 #include <iostream>
 2 #include <string.h>
 3 #include <string>
 4 #include <fstream>
 5 #include <algorithm>
 6 #include <stdio.h>
 7 #include <vector>
 8 #include <queue>
 9 #include <set>
10 #include <cmath>
11 using namespace std;
12 const double eps = 1e-8;
13 #define MAXN 1001
14 struct node
15 {
16     int x,y,z,p;
17 }star[MAXN];
18 int Distance(node a,node b)
19 {
20     return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
21 }
22 struct node1
23 {
24     int a,b;
25     int dist;
26 }dis[MAXN*MAXN];
27 bool cmp(node1 a,node1 b)
28 {
29     return a.dist<b.dist;
30 }
31 int minr;
32 int num,numd;
33 int N[MAXN];
34 int main()
35 {
36     int n;
37     while(scanf("%d",&n)!=EOF)
38     {
39         memset(dis,0,sizeof(dis));numd=0;
40         for(int i=0;i<n;i++)
41         {
42         scanf("%d%d%d%d",&star[i].x,&star[i].y,&star[i].z,&star[i].p);
43         N[i]=1;
44         for(int j=0;j<i;j++)
45         if(i!=j)
46         {dis[numd].a=i;dis[numd].b=j;dis[numd++].dist=Distance(star[i],star[j]);
47             }
48         }
49         num=0;minr=0;
50         sort(dis,dis+numd,cmp);
51         int tempn=0;
52         for(int i=0;i<numd;i++)
53         {
54             int temp=dis[i].dist;
55             while(i<numd&&dis[i].dist==temp){
56 
57             if(star[dis[i].b].p==star[dis[i].a].p)
58             {
59             N[dis[i].a]++;
60             N[dis[i].b]++;
61             if(N[dis[i].a]==0)tempn--;
62             if(N[dis[i].b]==0)tempn--;
63             }
64             else
65             {
66               N[dis[i].a]--;
67             N[dis[i].b]--;
68             if(N[dis[i].a]==-1)tempn++;
69             if(N[dis[i].b]==-1)tempn++;
70             }
71             i++;
72             }
73             i--;
74             /* temp=0;
75             for(int j=0;j<n;j++)
76             {
77             if(N[j][star[j].p]+1<N[j][star[j].p^1])temp++;
78             }*/
79             if(tempn>num){num=tempn;minr=dis[i].dist;}
80         }
81         printf("%d
%.4lf
",num,sqrt(minr*1.0));
82     }
83     return 0;
84 }

终于过了~