Advertisement
Guest User

Untitled

a guest
Jun 28th, 2017
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.12 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 ((O[i]-p).length() <= 3*(s.a-p).length())
  142.         {
  143.             ok = false;
  144.             cerr << i << " intercepts" << endl;
  145.         }
  146.     }
  147.     return ok;
  148. }
  149.  
  150. void dostep() {
  151.     cin >> NP;
  152.     for (int i = 0; i < NP; i++)
  153.         cin >> C[i].x >> C[i].y;
  154.     for (int i = 0; i < NP; i++)
  155.         cin >> O[i].x >> O[i].y;
  156.     cin >> goal.x >> goal.y;
  157.    
  158.     for (int v = 0; v < NP; v++)
  159.     {
  160.         join(in[v], out[v], 0, 1);
  161.         for (int i = 0; i < NP; i++)
  162.         {
  163.             if (i == v) continue;
  164.             segment s(C[v], C[i]);
  165.             cerr << "Passing " << v << " to " << i << endl;
  166.             if (pass(s))
  167.                 join(out[v], in[i], 0, 1);
  168.         }
  169.         cerr << "Passing " << v << " to goal" << endl;
  170.         segment s(C[v], goal);
  171.         if (pass(s))
  172.             join(out[v], drain, 0, 1);
  173.     }
  174.    
  175.     if (solve() < 2)
  176.         cout << "No ";
  177.     cout << "Goal" << endl;
  178. }
  179.  
  180. int main() {
  181.     int n;
  182.     cin >> n;
  183.     while(n--)dostep();
  184.     return 0;
  185. }
  186.  
  187. /*
  188. bauke@bauke-ubuntu:~/nwerc$ ./K < K.in
  189. Passing 0 to 1
  190. 1 intercepts
  191. 3 intercepts
  192. Passing 0 to 2
  193. 0 intercepts
  194. 2 intercepts
  195. Passing 0 to 3
  196. 0 intercepts
  197. 2 intercepts
  198. Passing 0 to goal
  199. 0 intercepts
  200. 2 intercepts
  201. 3 intercepts
  202. Passing 1 to 0
  203. 1 intercepts
  204. Passing 1 to 2
  205. 2 intercepts
  206. Passing 1 to 3
  207. 0 intercepts
  208. 1 intercepts
  209. 2 intercepts
  210. 3 intercepts
  211. Passing 1 to goal
  212. 0 intercepts
  213. 2 intercepts
  214. 3 intercepts
  215. Passing 2 to 0
  216. 0 intercepts
  217. 1 intercepts
  218. 2 intercepts
  219. Passing 2 to 1
  220. 0 intercepts
  221. 2 intercepts
  222. Passing 2 to 3
  223. 1 intercepts
  224. Passing 2 to goal
  225. 3 intercepts
  226. Passing 3 to 0
  227. 0 intercepts
  228. Passing 3 to 1
  229. 0 intercepts
  230. 1 intercepts
  231. 2 intercepts
  232. Passing 3 to 2
  233. 3 intercepts
  234. Passing 3 to goal
  235. 3 intercepts
  236. No Goal
  237. Passing 0 to 1
  238. Passing 0 to 2
  239. Passing 0 to 3
  240. Passing 0 to goal
  241. Passing 1 to 0
  242. Passing 1 to 2
  243. Passing 1 to 3
  244. 0 intercepts
  245. 3 intercepts
  246. Passing 1 to goal
  247. Passing 2 to 0
  248. Passing 2 to 1
  249. Passing 2 to 3
  250. Passing 2 to goal
  251. Passing 3 to 0
  252. Passing 3 to 1
  253. 0 intercepts
  254. 1 intercepts
  255. 2 intercepts
  256. 3 intercepts
  257. Passing 3 to 2
  258. Passing 3 to goal
  259. Goal
  260. Passing 0 to 1
  261. 0 intercepts
  262. Passing 0 to goal
  263. 0 intercepts
  264. Passing 1 to 0
  265. 0 intercepts
  266. Passing 1 to goal
  267. No Goal
  268. Passing 0 to 1
  269. 0 intercepts
  270. 1 intercepts
  271. Passing 0 to goal
  272. 0 intercepts
  273. 1 intercepts
  274. Passing 1 to 0
  275. 0 intercepts
  276. 1 intercepts
  277. Passing 1 to goal
  278. 0 intercepts
  279. 1 intercepts
  280. No Goal
  281. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement