UVA-1382, Distant Galaxy

找一個矩形

使的"邊上"的點的數目最大

我想了好久QAQ

要維持一個"ㄈ"字型的資料 這樣就可以在n^3內完成

啊就 第一次寫出來這類的題目有點爽呵呵

 1 #include <iostream>

 2 #include <cstdio>

 3 #include <cstdlib>

 4 #include <algorithm>

 5 #include <cstring>

 6 #include <set>

 7 #include <map>

 8 #include <list>

 9 using namespace std;

10 int main(){

11     int T=0;

12     set<int> tmpx;

13     set<int> tmpy;

14     set<int>::iterator tend, ti;

15     pair<map<int,int>::iterator, bool>tmppair;

16     map<int,int> transy;//map y cor to vector number

17     map<int,int> transx;//compress x cor

18     list<pair<int,int> > data;

19     int dot[105][105];

20     int sumx[105][105];

21     int sumy[105][105];

22     int tmpsum[105];

23     int right[105], left[105];

24     int n, x, y, cx, cy, ans, l;

25     while(scanf("%d", &n)){

26         if(n==0)break;

27         cx=cy=1;

28         tmpx.clear(); tmpy.clear();

29         transx.clear(); transy.clear();

30         memset(dot, 0, 101*101*4);

31         for(int i=0 ; i<n ; ++i){

32             scanf("%d%d", &x, &y);

33             tmpx.insert(x);

34             tmpy.insert(y);

35             data.push_back(pair<int,int>(x,y));

36         }

37         tend=tmpx.end();

38         for(ti=tmpx.begin() ; ti!=tend ; ti++){

39             transx[*ti]=cx++;

40         }

41         tend=tmpy.end();

42         for(ti=tmpy.begin() ; ti!=tend ; ti++){

43             transy[*ti]=cy++;

44         }

45         for(int i=0 ; i<n ; ++i){

46             dot[transx[data.front().first]][transy[data.front().second]]++;

47             data.pop_front();

48         }

49         for(int i=0 ; i<cy ; ++i){

50             sumx[0][i]=dot[0][i];

51             for(int j=1 ; j<cx ; ++j){

52                 sumx[j][i]=sumx[j-1][i]+dot[j][i];  // -

53             }

54         }

55         for(int i=0 ; i<cx ; ++i){

56             sumy[i][0]=dot[i][0];

57             for(int j=1 ; j<cy ; ++j){

58                 sumy[i][j]=sumy[i][j-1]+dot[i][j];  // |

59             }

60         }

61         ans=0;

62         for(int i=0 ; i<cy ; ++i){

63             for(int j=i+1 ; j<cy ; ++j){

64                 for(int k=0 ; k<cx ; ++k){

65                     tmpsum[k]=sumy[k][j]-sumy[k][i]-dot[k][j];

66                     right[k]=tmpsum[k]+sumx[k][i]+sumx[k][j];

67                     left[k]=tmpsum[k]-sumx[k][i]-sumx[k][j]+dot[k][i]+dot[k][j];

68                 }

69                 right[cx]=left[cx]=l=0;

70                 for(int k=1 ; k<cx ; ++k){

71                     ans=max(ans, left[l]+right[k]);

72                     if(left[k]>left[l]){

73                         l=k;

74                     }

75                 }

76             }

77         }

78         

79         printf("Case %d: %d\n",++T , ans);

80     }

81     return 0;

82 }