Cod sursă (job #553354)

#include <fstream>

using namespace std;

ifstream cin ("hex.in");
ofstream cout ("hex.out");

int n, x, y;

int rang[250005], t[250005], mn[250005], mx[250005], viz[250005];
int dx[] = {-1, -1, 0, 1, 1, 0};
int dy[] = {0, 1, 1, 0, -1, -1};

int find(int x) {
  int y = x, z;
  while(x != t[x])
    x = t[x];
  while(y != x) {
    z = t[y];
    t[y] = x;
    y = z;
  }
  return x;
}

void join(int x, int y) {
  if(rang[x] > rang[y])
    t[y] = x, mn[x] = min(mn[x], mn[y]), mx[x] = max(mx[x], mx[y]);
  else
    t[x] = y, mn[y] = min(mn[x], mn[y]), mx[y] = max(mx[x], mx[y]);
  if(rang[x] == rang[y])
    rang[y]++;
}

int main() {
  cin >> n;
  for(int i = 1; i <= n * n; i++)
    t[i] = i, mn[i] = n + 5, rang[i] = 1, viz[i] = -1;
  for(int i = 1; i <= n * n; i++) {
    cin >> x >> y;
    int val = x * (n - 1) + y;
    viz[val] = (i & 1);
    for(int j = 0; j < 6; j++) {
      int x2 = x + dx[j], y2 = y + dy[j], val2 = x2 * (n - 1) + y2;
      if(max(x2, y2) > n || min(x2, y2) < 1 || viz[val2] != (i & 1))
        continue;
      if(find(val) != find(val2))
        join(find(val), find(val2));
      if(i & 1)
        mn[find(val)] = min(mn[find(val)], y), mx[find(val)] = max(mx[find(val)], y);
      else
        mn[find(val)] = min(mn[find(val)], x), mx[find(val)] = max(mx[find(val)], x);
      if(mn[find(val)] == 1 && mx[find(val)] == n) {
        cout << i;
        return 0;
      }
    }
  }
  return 0;
}