BOJ 2261: 가장 가까운 두 점

작성일

https://www.acmicpc.net/problem/2261

  • 2월동안 187문제 풀기(지난달 누적 87개) (43/187)
  • 알고리즘 교과서에 있었던것 같은 문제.
  • 처음에는 축별로 나눠서 자료구조를 만들어서 실패
  • 두 번째 이후에 엄청나게 오답이 나왔었는데 -_-.. 변수 이름 잘못적은거 하나랑, unsigned int에 당한거 하나
  • 특히나 size_t에 당한 부분은 반드시 기억해서 담에는 실수하지 말자. 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    #include <bits/stdc++.h>
using namespace std;

int main() {
  vector<int> x;
  cout << (0 < x.size()-1); // True
  for(int i = 0; i < x.size()-1; i++)
    cout << "Hello!"; // Infinte Loop
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <bits/stdc++.h>
using namespace std;

long long N, B;

struct Mat {
  vector<vector<int>> arr;

	Mat() {
	  arr.resize(N, vector<int>(N));
  }

  Mat operator*(Mat& b) {
    Mat ans;
    for(int i = 0; i < N; i++)
      for(int j = 0; j < N; j++)
        for(int k = 0; k < N; k++) {
          int tmp = (arr[i][k] * b.arr[k][j]) % 1000;
          ans.arr[i][j] = (ans.arr[i][j] + tmp) % 1000;
        }
    return ans;
  }

  Mat& operator=(Mat b) {
    for(int i = 0; i < N; i++)
      for(int j = 0; j < N; j++)
          arr[i][j] = b.arr[i][j];
    return *this;
  }

  void print() {
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++)
        cout << arr[i][j] << " ";
      cout << "\n";
    }
  }
};

Mat pow(Mat A, long long e) {
  Mat ret;
  for(int i = 0; i < N; i++)
    ret.arr[i][i] = 1;
  while(e) {
    if(e&1) ret = ret * A;
    e /= 2;
    A = A * A;
  }
  return ret;
}

int main() {
  ios::sync_with_stdio(false);
  cin >> N >> B;
  Mat A;
  for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++)
      cin >> A.arr[i][j];
  pow(A, B).print();
  return 0;
}#include <bits/stdc++.h>
using namespace std;
#include <sys/stat.h>
#include <sys/mman.h>
class fio {
  size_t rsize;
  unsigned char* rbuf;
  int ridx;

  public:
  fio() : ridx(0) {
    struct stat rstat;
    fstat(0, &rstat);
    rsize = rstat.st_size;
    rbuf = (unsigned char*)mmap(0,rsize,PROT_READ,MAP_FILE|MAP_PRIVATE,0,0);
  }

  inline bool isBlank() {
    return
      rbuf[ridx] == '\n' || rbuf[ridx] == '\t' || rbuf[ridx] == '\r' ||
      rbuf[ridx] == '\f' || rbuf[ridx] == '\v' || rbuf[ridx] == ' ';
  }
  inline void consumeBlank() { while (isBlank()) ridx++; }

  inline int readInt(){
    int res = 0, flag = 0;
    consumeBlank();
    if (rbuf[ridx] == '-'){
      flag = 1;
      ridx++;
    }
    while (!isBlank() && ridx < rsize)
      res = 10 * res + rbuf[ridx++] - '0';
    return flag ? -res : res;
  }
};

fio io;

struct Coord { int x, y; };
int N;
vector<Coord> arr;

inline int D(Coord& a, Coord& b) {
  int dx = b.x-a.x;
  int dy = b.y-a.y;
  return dx*dx+dy*dy;
}
void fillInput() {
	N = io.readInt();
  for(int i = 0; i < N; i++) {
		int x = io.readInt();
		int y = io.readInt();
    arr.push_back({x,y});
  }
  auto cmp = [](Coord& a, Coord& b) { return a.x < b.x; };
  sort(arr.begin(), arr.end(), cmp);
}

int go(int l, int r) {
  if(l+1 == r) return D(arr[l],arr[r]);
  if(l+2 == r) return min({D(arr[l],arr[l+1]), D(arr[l],arr[r]), D(arr[l+1],arr[r])});

  int m = (l+r)/2;
  int d = min(go(l,m),go(m+1,r));
  int line = (arr[m].x + arr[m+1].x)/2;

  vector<Coord> candi;
  candi.reserve(r-l+1);
  for(int i = l; i <= r; i++) {
    int diff = arr[i].x - line;
    if(diff*diff < d)
      candi.push_back(arr[i]);
  }
  if(candi.empty()) return d;

  auto cmp = [](Coord& a, Coord& b) { return a.y < b.y; };
  sort(candi.begin(), candi.end(), cmp);

  int len = candi.size(); // size_t를 주의하라
  for(int i = 0; i < len; i++) {
    for(int j = i+1; j < len; j++) {
      int diff = candi[j].y - candi[i].y;
      if(diff*diff >= d) break;
      d = min(d, D(candi[j], candi[i]));
    }
  }
  return d;
}

int main() {
  fillInput();
  cout << go(0, arr.size()-1);
}