Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdlib>
- #include <cstdio>
- #include <cstring>
- #include <cmath>
- #include <string>
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <queue>
- #include <list>
- #include <stack>
- using namespace std;
- typedef double TP;
- struct point {
- TP x,y;
- point() {}
- point(TP nx, TP ny) : x(nx), y(ny) {}
- point conj() const { return point(x, -y); }
- point operator+(const point &p) const { return point(x + p.x, y + p.y); }
- point operator-(const point &p) const { return point(x - p.x, y - p.y); }
- point operator*(const TP c) const { return point(x * c, y * c); }
- point operator*(const point &p) const { return point((x * p.x) - (y * p.y), (x * p.y) + (y * p.x)); }
- point operator/(const TP c) const { return point(x / c, y / c); }
- point operator/(const point &p) const { return (*this * p.conj()) / (p.x * p.x + p.y * p.y); }
- bool operator==(const point &p) const { return (abs(x-p.x) < 1e-6) && (abs(y-p.y) < 1e-6); }
- double length() const { return hypot(x, y); }
- double arg() const { return atan2(y, x); }
- TP dot(const point &p) const { return (x * p.x) + (y * p.y); }
- TP cross(const point &p) const { return (x * p.y) - (p.x * y); }
- };
- point polar(const TP l, const TP h) { return point((l * cos(h)), (l * sin(h))); }
- struct segment { // INCOMPLEET
- point a,b;
- segment(const point &na, const point &nb) : a(na), b(nb) {}
- point project(const point &p) const { double l = (p-a).dot(b-a)/(b-a).dot(b-a); if (l<0) l = 0; if (l > 1) l = 1; return a + (b-a)*l; }
- bool proj(const point &p, point &t) const {
- double l = (p-a).dot(b-a) / (b-a).dot(b-a);
- if (l < 0)
- return false;
- if (l > 1)
- return false;
- t = a + (b-a)*l;
- return true;
- }
- double dist(const point &p) const { return (p - project(p)).length(); }
- };
- #define MAX_FLOWS 1000
- struct node;
- int flows[MAX_FLOWS];
- int flowcnt = 0;
- int last_tag = 0;
- struct tube {
- node *next;
- int dir, mx, *flow;
- tube(node *nnext, int ndir, int nmx, int *nflow) : next(nnext), dir(ndir), mx(nmx), flow(nflow) {}
- int free() { return mx - dir**flow; }
- void add(int amount) { *flow+= dir*amount; }
- };
- struct node {
- vector<tube> tubes;
- int tag;
- node() : tag(0) {}
- void reset() { tubes.clear(); tag = 0; }
- };
- void join(node &a, node &b, int maxtoa, int maxtob) {
- a.tubes.push_back(tube(&b, 1, maxtob, flows+flowcnt));
- b.tubes.push_back(tube(&a,-1, maxtoa, flows+flowcnt));
- flows[flowcnt] = 0;
- flowcnt++;
- }
- int NP;
- point C[50];
- point O[50];
- point goal;
- node in[50];
- node out[50];
- vector<tube*> path;
- node &source = out[0];
- node drain;
- int findpath(node *cur) {
- if (cur == &drain) return 0x3fffffff;
- cur->tag = last_tag;
- for (unsigned int i = 0; i < cur->tubes.size(); i++) {
- tube *t = &cur->tubes[i];
- if (t->next->tag < last_tag && t->free()) {
- int cap = findpath(t->next);
- if (cap > 0) {
- path.push_back(t);
- return min(cap, t->free());
- }
- }
- }
- return 0;
- }
- int solve() {
- int cap;
- int flow = 0;
- last_tag = 1;
- while ((cap = findpath(&source))) {
- for (unsigned int i = 0; i < path.size(); i++)
- path[i]->add(cap);
- flow += cap;
- path.clear();
- last_tag++;
- }
- return flow;
- }
- void reset() {
- source.reset();
- drain.reset();
- flowcnt = 0;
- }
- bool pass(const segment &s) {
- bool ok = true;
- for (int i = 0; i < NP; i++)
- {
- point p;
- if (!s.proj(O[i], p))
- continue;
- if (3*(O[i]-p).length() <= (s.a-p).length())
- {
- ok = false;
- //cerr << i << " intercepts" << endl;
- }
- }
- return ok;
- }
- void dostep() {
- reset();
- for (int i = 0; i < 50; i++)
- {
- in[i].reset();
- out[i].reset();
- }
- cin >> NP;
- for (int i = 0; i < NP; i++)
- cin >> C[i].x >> C[i].y;
- for (int i = 0; i < NP; i++)
- cin >> O[i].x >> O[i].y;
- cin >> goal.x >> goal.y;
- for (int v = 0; v < NP; v++)
- {
- join(in[v], out[v], 0, 1);
- for (int i = 0; i < NP; i++)
- {
- if (i == v) continue;
- segment s(C[v], C[i]);
- //cerr << "Passing " << v << " to " << i << endl;
- if (pass(s))
- join(out[v], in[i], 0, 1000);
- }
- //cerr << "Passing " << v << " to goal" << endl;
- segment s(C[v], goal);
- if (pass(s))
- join(out[v], drain, 0, 1000);
- }
- //cerr << solve() << endl;
- if (solve() < 2)
- cout << "No ";
- cout << "Goal" << endl;
- }
- int main() {
- int n;
- cin >> n;
- while(n--)dostep();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement