Hämähäkit

// E

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

using namespace std;

typedef long long int ll;
typedef pair<ll, ll> P;

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

struct angle_cmp {
  ll x, y;
  angle_cmp(int i) : x(poss[i].first), y(poss[i].second) {}
  angle_cmp(ll x, ll y) : x(x), y(y) {}
  
  static const int quad(const ll x, const ll y) {
    // 0 | 1
    // -----
    // 3 | 2
    if (y < 0) {
      if (x < 0)
	return 0;
      return 1;
    }
    if (x > 0)
      return 2;
    return 3;
  }
  
  bool operator()(const int a, const int b) const {
    ll ax = poss[a].first - x;
    ll ay = poss[a].second - y;
    ll bx = poss[b].first - x;
    ll by = poss[b].second - y;
    
    int aq = quad(ax, ay);
    int bq = quad(bx, by);
    if (aq != bq) return aq < bq;
    
    return ax*by - ay*bx > 0;
  }
};
struct y_cmp {
  bool operator()(const int a, const int b) const {
    return poss[a].second < poss[b].second;
  }
};

bool findRoute(int i) {
  if (!exists[i])
    return false;
  exists[i] = 0;
  
  if (poss[i].first == w)
    return true;
  
  for (int con : cons[i]) {
    if (findRoute(con))
      return true;
  }
  return false;
}

int main() {
  cin >> n >> m >> w;
  vector<int> starts;
  for (int i = 1; i <= n; i++) {
    cin >> poss[i].first >> poss[i].second;
    if (poss[i].first == 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);
  }
  
  for (int i = 1; i <= n; i++) {
    sort(cons[i].begin(), cons[i].end(), angle_cmp(i));
  }
  
  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: WRONG ANSWER

Test 24

Group: 2

Verdict: WRONG ANSWER

Test 25

Group: 2

Verdict: ACCEPTED

Test 26

Group: 2

Verdict: WRONG ANSWER

Test 27

Group: 2

Verdict: ACCEPTED

Test 28

Group: 2

Verdict: ACCEPTED

Test 29

Group: 2

Verdict: WRONG ANSWER

Test 30

Group: 2

Verdict: ACCEPTED

Test 31

Group: 2

Verdict: WRONG ANSWER

Test 32

Group: 2

Verdict: ACCEPTED

Test 33

Group: 2

Verdict: ACCEPTED

Test 34

Group: 2

Verdict: WRONG ANSWER

Test 35

Group: 2

Verdict: WRONG ANSWER

Test 36

Group: 2

Verdict: ACCEPTED

Test 37

Group: 2

Verdict: ACCEPTED

Test 38

Group: 2

Verdict: WRONG ANSWER

Test 39

Group: 2

Verdict: WRONG ANSWER

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: WRONG ANSWER

Test 46

Group: 3

Verdict: ACCEPTED

Test 47

Group: 3

Verdict: ACCEPTED

Test 48

Group: 3

Verdict: WRONG ANSWER

Test 49

Group: 3

Verdict: ACCEPTED

Test 50

Group: 3

Verdict: WRONG ANSWER

Test 51

Group: 3

Verdict: WRONG ANSWER

Test 52

Group: 3

Verdict: WRONG ANSWER

Test 53

Group: 3

Verdict: WRONG ANSWER

Test 54

Group: 3

Verdict: ACCEPTED

Test 55

Group: 3

Verdict: WRONG ANSWER

Test 56

Group: 3

Verdict: ACCEPTED

Test 57

Group: 3

Verdict: WRONG ANSWER

Test 58

Group: 3

Verdict: WRONG ANSWER

Test 59

Group: 3

Verdict: WRONG ANSWER

Test 60

Group: 3

Verdict: WRONG ANSWER

Test 61

Group: 3

Verdict: ACCEPTED

Test 62

Group: 3

Verdict: ACCEPTED

Test 63

Group: 3

Verdict: WRONG ANSWER

Test 64

Group: 3

Verdict: WRONG ANSWER

Test 65

Group: 3

Verdict: ACCEPTED

Test 66

Group: 3

Verdict: ACCEPTED