Advertisement
Guest User

Untitled

a guest
Jun 28th, 2017
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.88 KB | None | 0 0
  1. #include <cstdlib>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <string>
  6. #include <iostream>
  7. #include <algorithm>
  8. #include <vector>
  9. #include <queue>
  10. #include <list>
  11. #include <stack>
  12.  
  13. using namespace std;
  14.  
  15. typedef double TP;
  16.  
  17. struct point {
  18.     TP x,y;
  19.    
  20.     point() {}
  21.     point(TP nx, TP ny) : x(nx), y(ny) {}
  22.     point conj() const { return point(x, -y); }
  23.     point operator+(const point &p) const { return point(x + p.x, y + p.y); }
  24.     point operator-(const point &p) const { return point(x - p.x, y - p.y); }
  25.     point operator*(const TP c) const { return point(x * c, y * c); }
  26.     point operator*(const point &p) const { return point((x * p.x) - (y * p.y), (x * p.y) + (y * p.x)); }
  27.     point operator/(const TP c) const { return point(x / c, y / c); }
  28.     point operator/(const point &p) const { return (*this * p.conj()) / (p.x * p.x + p.y * p.y); }
  29.     bool operator==(const point &p) const { return (abs(x-p.x) < 1e-6) && (abs(y-p.y) < 1e-6); }
  30.     double length() const { return hypot(x, y); }
  31.     double arg() const { return atan2(y, x); }
  32.     TP dot(const point &p) const { return (x * p.x) + (y * p.y); }
  33.     TP cross(const point &p) const { return (x * p.y) - (p.x * y); }
  34. };
  35.  
  36. point polar(const TP l, const TP h) { return point((l * cos(h)), (l * sin(h))); }
  37.  
  38. struct segment { // INCOMPLEET
  39.     point a,b;
  40.    
  41.     segment(const point &na, const point &nb) : a(na), b(nb) {}
  42.     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; }
  43.    
  44.     bool proj(const point &p, point &t) const {
  45.         double l = (p-a).dot(b-a) / (b-a).dot(b-a);
  46.         if (l < 0)
  47.             return false;
  48.         if (l > 1)
  49.             return false;
  50.         t = a + (b-a)*l;
  51.         return true;
  52.     }
  53.    
  54.     double dist(const point &p) const { return (p - project(p)).length(); }
  55. };
  56.  
  57. #define MAX_FLOWS 1000
  58.  
  59. struct node;
  60. int flows[MAX_FLOWS];
  61. int flowcnt = 0;
  62. int last_tag = 0;
  63.  
  64. struct tube {
  65.     node *next;
  66.     int dir, mx, *flow;
  67.     tube(node *nnext, int ndir, int nmx, int *nflow) : next(nnext), dir(ndir), mx(nmx), flow(nflow) {}
  68.     int free() { return mx - dir**flow; }
  69.     void add(int amount) { *flow+= dir*amount; }
  70. };
  71.  
  72. struct node {
  73.     vector<tube> tubes;
  74.     int tag;
  75.     node() : tag(0) {}
  76.     void reset() { tubes.clear(); tag = 0; }
  77. };
  78.  
  79. void join(node &a, node &b, int maxtoa, int maxtob) {
  80.     a.tubes.push_back(tube(&b, 1, maxtob, flows+flowcnt));
  81.     b.tubes.push_back(tube(&a,-1, maxtoa, flows+flowcnt));
  82.     flows[flowcnt] = 0;
  83.     flowcnt++;
  84. }
  85.  
  86. int NP;
  87. point C[50];
  88. point O[50];
  89. point goal;
  90.  
  91. node in[50];
  92. node out[50];
  93.  
  94. vector<tube*> path;
  95. node &source = out[0];
  96. node drain;
  97. int findpath(node *cur) {
  98.     if (cur == &drain) return 0x3fffffff;
  99.     cur->tag = last_tag;
  100.     for (unsigned int i = 0; i < cur->tubes.size(); i++) {
  101.         tube *t = &cur->tubes[i];
  102.         if (t->next->tag < last_tag && t->free()) {
  103.             int cap = findpath(t->next);
  104.             if (cap > 0) {
  105.                 path.push_back(t);
  106.                 return min(cap, t->free());
  107.             }
  108.         }
  109.     }
  110.     return 0;
  111. }
  112.  
  113. int solve() {
  114.     int cap;
  115.     int flow = 0;
  116.     last_tag = 1;
  117.     while ((cap = findpath(&source))) {
  118.         for (unsigned int i = 0; i < path.size(); i++)
  119.             path[i]->add(cap);
  120.         flow += cap;
  121.         path.clear();
  122.         last_tag++;
  123.     }
  124.    
  125.     return flow;
  126. }
  127.  
  128. void reset() {
  129.     source.reset();
  130.     drain.reset();
  131.     flowcnt = 0;
  132. }
  133.  
  134. bool pass(const segment &s) {
  135.     bool ok = true;
  136.     for (int i = 0; i < NP; i++)
  137.     {
  138.         point p;
  139.         if (!s.proj(O[i], p))
  140.             continue;
  141.         if (p.length() <= 3*(s.a-p).length()) {
  142.             ok = false;
  143.             cerr << i << " intercepts" << endl;
  144.         }
  145.     }
  146.     return ok;
  147. }
  148.  
  149. void dostep() {
  150.     cin >> NP;
  151.     for (int i = 0; i < NP; i++)
  152.         cin >> C[i].x >> C[i].y;
  153.     for (int i = 0; i < NP; i++)
  154.         cin >> O[i].x >> O[i].y;
  155.     cin >> goal.x >> goal.y;
  156.    
  157.     for (int v = 0; v < NP; v++)
  158.     {
  159.         join(in[v], out[v], 0, 1);
  160.         for (int i = 0; i < NP; i++)
  161.         {
  162.             if (i == v) continue;
  163.             segment s(C[v], C[i]);
  164.             cerr << "Passing " << v << " to " << i << endl;
  165.             if (pass(s))
  166.                 join(out[v], in[i], 0, 1);
  167.         }
  168.         cerr << "Passing " << v << " to goal" << endl;
  169.         segment s(C[v], goal);
  170.         if (pass(s))
  171.             join(out[v], drain, 0, 1);
  172.     }
  173.    
  174.     if (solve() < 2)
  175.         cout << "No ";
  176.     cout << "Goal" << endl;
  177. }
  178.  
  179. int main() {
  180.     int n;
  181.     cin >> n;
  182.     while(n--)dostep();
  183.     return 0;
  184. }
  185.  
  186.  
  187. /*
  188. bauke@bauke-ubuntu:~/nwerc$ ./K < K.in
  189. Passing 0 to 1
  190. 3 intercepts
  191. Passing 0 to 2
  192. 2 intercepts
  193. Passing 0 to 3
  194. Passing 0 to goal
  195. 2 intercepts
  196. 3 intercepts
  197. Passing 1 to 0
  198. Passing 1 to 2
  199. 2 intercepts
  200. Passing 1 to 3
  201. 0 intercepts
  202. 3 intercepts
  203. Passing 1 to goal
  204. 0 intercepts
  205. 3 intercepts
  206. Passing 2 to 0
  207. 0 intercepts
  208. 1 intercepts
  209. Passing 2 to 1
  210. 0 intercepts
  211. 2 intercepts
  212. Passing 2 to 3
  213. 1 intercepts
  214. Passing 2 to goal
  215. 3 intercepts
  216. Passing 3 to 0
  217. Passing 3 to 1
  218. 1 intercepts
  219. 2 intercepts
  220. Passing 3 to 2
  221. 3 intercepts
  222. Passing 3 to goal
  223. 3 intercepts
  224. No Goal
  225. Passing 0 to 1
  226. Passing 0 to 2
  227. Passing 0 to 3
  228. Passing 0 to goal
  229. Passing 1 to 0
  230. Passing 1 to 2
  231. Passing 1 to 3
  232. 0 intercepts
  233. Passing 1 to goal
  234. Passing 2 to 0
  235. Passing 2 to 1
  236. Passing 2 to 3
  237. Passing 2 to goal
  238. Passing 3 to 0
  239. Passing 3 to 1
  240. 0 intercepts
  241. 1 intercepts
  242. 2 intercepts
  243. 3 intercepts
  244. Passing 3 to 2
  245. Passing 3 to goal
  246. Goal
  247. Passing 0 to 1
  248. 0 intercepts
  249. Passing 0 to goal
  250. 0 intercepts
  251. 1 intercepts
  252. Passing 1 to 0
  253. 0 intercepts
  254. Passing 1 to goal
  255. No Goal
  256. Passing 0 to 1
  257. 0 intercepts
  258. Passing 0 to goal
  259. 0 intercepts
  260. 1 intercepts
  261. Passing 1 to 0
  262. Passing 1 to goal
  263. 1 intercepts
  264. No Goal
  265. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement