Hämähäkit

// E

#include <iostream>
#include <vector>
#include <algorithm>
#include <complex>

using namespace std;

typedef long double ll;
typedef complex<ll> P;

P poss[100100];
bool exists[100100];
vector<int> cons[100100];
int n, m;
ll w;

struct angle_cmp {
  P center;
  P rot;
  angle_cmp(P center) : center(center), rot(P(1, 0)) {}
  angle_cmp(P center, P rot) : center(center), rot(rot) {}
  
  static const int quad(const P p) {
    // 0 | 1
    // -----
    // 3 | 2
    const ll y = p.imag();
    const ll x = p.real();
    if (y < 0) {
      if (x < 0)
	return 0;
      return 1;
    }
    if (x > 0)
      return 2;
    return 3;
  }
  
  bool operator()(const int ai, const int bi) const {
    P a = (poss[ai] - center) * rot;
    P b = (poss[bi] - center) * rot;
    
    int aq = quad(a);
    int bq = quad(b);
    if (aq != bq) return aq < bq;
    
    return a.real()*b.imag() - a.imag()*b.real() > 0;
  }
};
struct y_cmp {
  bool operator()(const int a, const int b) const {
    return poss[a].imag() < poss[b].imag();
  }
};

bool findRoute(int i, int j = -1) {
  if (!exists[i])
    return false;
  exists[i] = 0;
  
  if (poss[i].real() == w)
    return true;
  
  if (j != -1) {
    sort(cons[i].begin(), cons[i].end(), angle_cmp(poss[i], conj(poss[i]-poss[j])));
  } else {
    sort(cons[i].begin(), cons[i].end(), angle_cmp(poss[i]));
  }
  for (int con : cons[i]) {
    if (findRoute(con, i))
      return true;
  }
  return false;
}

int main() {
  cin >> n >> m >> w;
  vector<int> starts;
  for (int i = 1; i <= n; i++) {
    ll x, y;
    cin >> x >> y;
    poss[i].real(x);
    poss[i].imag(y);
    if (poss[i].real() == 0)
      starts.push_back(i);
    exists[i] = 1;
  }
  
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    cons[a].push_back(b);
    cons[b].push_back(a);
  }
  
  int res = 0;
  sort(starts.begin(), starts.end(), y_cmp());
  for (int start : starts) {
    res += findRoute(start);
  }
  
  cout<<res<<'\n';
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: ACCEPTED

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 1

Verdict: ACCEPTED

Test 12

Group: 1

Verdict: ACCEPTED

Test 13

Group: 1

Verdict: ACCEPTED

Test 14

Group: 1

Verdict: ACCEPTED

Test 15

Group: 1

Verdict: ACCEPTED

Test 16

Group: 1

Verdict: ACCEPTED

Test 17

Group: 1

Verdict: ACCEPTED

Test 18

Group: 1

Verdict: ACCEPTED

Test 19

Group: 1

Verdict: ACCEPTED

Test 20

Group: 1

Verdict: ACCEPTED

Test 21

Group: 1

Verdict: ACCEPTED

Test 22

Group: 1

Verdict: ACCEPTED

Test 23

Group: 2

Verdict: ACCEPTED

Test 24

Group: 2

Verdict: ACCEPTED

Test 25

Group: 2

Verdict: ACCEPTED

Test 26

Group: 2

Verdict: ACCEPTED

Test 27

Group: 2

Verdict: ACCEPTED

Test 28

Group: 2

Verdict: ACCEPTED

Test 29

Group: 2

Verdict: ACCEPTED

Test 30

Group: 2

Verdict: ACCEPTED

Test 31

Group: 2

Verdict: ACCEPTED

Test 32

Group: 2

Verdict: ACCEPTED

Test 33

Group: 2

Verdict: ACCEPTED

Test 34

Group: 2

Verdict: ACCEPTED

Test 35

Group: 2

Verdict: ACCEPTED

Test 36

Group: 2

Verdict: ACCEPTED

Test 37

Group: 2

Verdict: ACCEPTED

Test 38

Group: 2

Verdict: ACCEPTED

Test 39

Group: 2

Verdict: ACCEPTED

Test 40

Group: 2

Verdict: ACCEPTED

Test 41

Group: 2

Verdict: ACCEPTED

Test 42

Group: 2

Verdict: ACCEPTED

Test 43

Group: 2

Verdict: ACCEPTED

Test 44

Group: 2

Verdict: ACCEPTED

Test 45

Group: 3

Verdict: ACCEPTED

Test 46

Group: 3

Verdict: ACCEPTED

Test 47

Group: 3

Verdict: ACCEPTED

Test 48

Group: 3

Verdict: ACCEPTED

Test 49

Group: 3

Verdict: ACCEPTED

Test 50

Group: 3

Verdict: ACCEPTED

Test 51

Group: 3

Verdict: ACCEPTED

Test 52

Group: 3

Verdict: ACCEPTED

Test 53

Group: 3

Verdict: ACCEPTED

Test 54

Group: 3

Verdict: ACCEPTED

Test 55

Group: 3

Verdict: ACCEPTED

Test 56

Group: 3

Verdict: ACCEPTED

Test 57

Group: 3

Verdict: ACCEPTED

Test 58

Group: 3

Verdict: ACCEPTED

Test 59

Group: 3

Verdict: ACCEPTED

Test 60

Group: 3

Verdict: ACCEPTED

Test 61

Group: 3

Verdict: ACCEPTED

Test 62

Group: 3

Verdict: ACCEPTED

Test 63

Group: 3

Verdict: ACCEPTED

Test 64

Group: 3

Verdict: ACCEPTED

Test 65

Group: 3

Verdict: ACCEPTED

Test 66

Group: 3

Verdict: ACCEPTED