API tools faq
paste
Advertisement
PikMike

Untitled

PikMike
Aug 15th, 2017
381
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 12.61 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2.  
  3. #define pb push_back
  4. #define mp make_pair
  5. #define sz(x) (int)(x).size()
  6. #define li long long
  7. #define ld long double
  8. #define x first
  9. #define y second
  10. #define pt pair<li, li>
  11. #define pll pair<ll, ll>
  12. #define forn(i, t) for(int i = 0; i < (t); i++)
  13. #define fore(i, f, t) for(int i = (f); i < (t); i++)
  14. #define forr(i, f, t) for(int i = (f) - 1; i >= (t); i--)
  15. #define all(x) (x).begin(), (x).end()
  16. #define ins insert
  17.  
  18. using namespace std;
  19.  
  20.  
  21. const int INF = 1e9;
  22. const int MOD = 1e9 + 7;
  23. const li INF64 = 1e18;
  24. const ld EPS = 1e-7;
  25.  
  26. mt19937 myrand(time(NULL));
  27.  
  28. const int N = 53;
  29.  
  30. int n, R;
  31. pt a[N];
  32. int b[N], d[N];
  33. int f[3 * N][3 * N];
  34. vector<int> cx, cy;
  35. pt pos[N][5];
  36.  
  37.  
  38. void upd(int x, int y){
  39.     for (int i = x; i < 3 * N; i |= i + 1)
  40.         for (int j = y; j < 3 * N; j |= j + 1)
  41.             f[i][j]++;
  42. }
  43.  
  44.  
  45. int get(int x, int y){
  46.     int sum = 0;
  47.     for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
  48.         for (int j = y; j >= 0; j = (j & (j + 1)) - 1)
  49.             sum += f[i][j];
  50.     return sum;
  51. }
  52.  
  53.  
  54. pt operator -(const pt a, const pt b){
  55.     return mp(a.x - b.x, a.y - b.y);
  56. }
  57.  
  58.  
  59. struct Circle{
  60.     double x, y, r;
  61.    
  62.     Circle(pt a){
  63.         x = a.x;
  64.         y = a.y;
  65.         r = 0.1;
  66.     };
  67.    
  68.     Circle(pt a, pt b){
  69.         x = (a.x + b.x) / 2.0;
  70.         y = (a.y + b.y) / 2.0;
  71.         r = hypot(a.x - b.x, a.y - b.y) / 2;
  72.     };
  73.    
  74.     Circle(pt a, pt b, pt c){
  75.         double d = 2.0 * (a.x * b.y + a.y * c.x + b.x * c.y - a.x * c.y - a.y * b.x - b.y * c.x);
  76.         double aa = a.x * a.x + a.y * a.y, bb = b.x * b.x + b.y * b.y, cc = c.x * c.x + c.y * c.y;
  77.         x = (aa * b.y + a.y * cc + bb * c.y - aa * c.y - a.y * bb - b.y * cc) * 1.0 / d;
  78.         y = -(aa * b.x + a.x * cc + bb * c.x - aa * c.x - a.x * bb - b.x * cc) * 1.0 / d;
  79.         r = (double)(hypotl(a.x - b.x, a.y - b.y) * hypotl(a.x - c.x, a.y - c.y) * hypotl(b.x - c.x, b.y - c.y) / ((b - a).x * (c - a).y - (b - a).y * (c - a).x) / 2);
  80.     };
  81.    
  82.     Circle(){};
  83. };
  84.  
  85.  
  86. struct Line{
  87.     double A, B, C;
  88.     Line(pt a, pt b){
  89.         A = b.y - a.y;
  90.         B = a.x - b.x;
  91.         C = -A * a.x - B * a.y;
  92.     };
  93.     Line(){};
  94. };
  95.  
  96.  
  97. bool isOn(pt a, Line l){
  98.     return (l.A * a.x + l.B * a.y + l.C == 0);
  99. }
  100.  
  101.  
  102. bool read(){
  103.     if(scanf("%d%d", &n, &R) != 2)
  104.         return 0;
  105.     forn(i, n)
  106.         scanf("%lld%lld", &a[i].x, &a[i].y);
  107.     return 1;
  108. }
  109.  
  110.  
  111. pt dt[4] = {{1, 1}, {-1,- 1}, {1, -1}, {-1, 1}};
  112.  
  113.  
  114. int check1(Line l){
  115.     int cnt1 = 0, cnt2 = 0;
  116.     forn(i, n)
  117.         if (l.A * a[i].x + l.B * a[i].y + l.C < EPS)
  118.             b[cnt1++] = i;
  119.         else
  120.             d[cnt2++] = i;
  121.            
  122.     /*forn(i, cnt1)
  123.         printf("[%d %d] ", a[b[i]].x, a[b[i]].y);
  124.     printf("\n");
  125.    
  126.     forn(i, cnt2)
  127.         printf("[%d %d] ", a[d[i]].x, a[d[i]].y);
  128.     printf("\n\n");*/
  129.    
  130.     memset(f, 0, sizeof(f));
  131.  
  132.     forn(i, cnt1)
  133.         upd(pos[b[i]][0].x, pos[b[i]][0].y);
  134.    
  135.     int res1 = 0, res2 = 0;
  136.    
  137.     int x1, x2, y1, y2;
  138.     int cur;
  139.     forn(i, cnt1)
  140.         fore(j, i + 1, cnt1)
  141.             if ((a[b[i]].x > a[b[j]].x && a[b[i]].y < a[b[j]].y) || (a[b[i]].x < a[b[j]].x && a[b[i]].y > a[b[j]].y)){
  142.                 x1 = min(pos[b[i]][0].x, pos[b[j]][0].x);
  143.                 y1 = min(pos[b[i]][0].y, pos[b[j]][0].y);
  144.                 x2 = min(pos[b[i]][1].x, pos[b[j]][1].x);
  145.                 y2 = min(pos[b[i]][1].y, pos[b[j]][1].y);
  146.                
  147.                 cur = get(x2, y2) - get(x1 - 1, y2) - get(x2, y1 - 1) + get(x1 - 1, y1 - 1);
  148.                 res1 = max(cur, res1);
  149.                
  150.                 x1 = max(pos[b[i]][0].x, pos[b[j]][0].x);
  151.                 y1 = max(pos[b[i]][0].y, pos[b[j]][0].y);
  152.                 x2 = max(pos[b[i]][2].x, pos[b[j]][2].x);
  153.                 y2 = max(pos[b[i]][2].y, pos[b[j]][2].y);
  154.                
  155.                 cur = get(x1, y1) - get(x2 - 1, y1) - get(x1, y2 - 1) + get(x2 - 1, y2 - 1);
  156.                 res1 = max(cur, res1);
  157.             }
  158.             else{
  159.                 x1 = min(pos[b[i]][0].x, pos[b[j]][0].x);
  160.                 y1 = max(pos[b[i]][0].y, pos[b[j]][0].y);
  161.                 x2 = min(pos[b[i]][1].x, pos[b[j]][1].x);
  162.                 y2 = max(pos[b[i]][2].y, pos[b[j]][2].y);
  163.                
  164.                 cur = get(x2, y1) - get(x1 - 1, y1) - get(x2, y2 - 1) + get(x1 - 1, y2 - 1);
  165.                 res1 = max(cur, res1);
  166.                
  167.                 x1 = max(pos[b[i]][0].x, pos[b[j]][0].x);
  168.                 y1 = min(pos[b[i]][0].y, pos[b[j]][0].y);
  169.                 x2 = max(pos[b[i]][2].x, pos[b[j]][2].x);
  170.                 y2 = min(pos[b[i]][1].y, pos[b[j]][1].y);
  171.                
  172.                 cur = get(x1, y2) - get(x2 - 1, y2) - get(x1, y1 - 1) + get(x2 - 1, y1 - 1);
  173.                 res1 = max(cur, res1);
  174.             }
  175.            
  176.     forn(i, cnt1){
  177.         x1 = pos[b[i]][0].x;
  178.         y1 = pos[b[i]][0].y;
  179.         forn(j, 4){
  180.             x2 = pos[b[i]][dt[j].x > 0 ? 1 : 2].x;
  181.             y2 = pos[b[i]][dt[j].y > 0 ? 1 : 2].y;
  182.            
  183.             cur = get(max(x1, x2), max(y1, y2)) -
  184.                   get(min(x1, x2) - 1, max(y1, y2)) -
  185.                   get(max(x1, x2), min(y1, y2) - 1) +
  186.                   get(min(x1, x2) - 1, min(y1, y2) - 1);
  187.             res1 = max(res1, cur);
  188.         }
  189.     }
  190.        
  191.     memset(f, 0, sizeof(f));
  192.  
  193.     forn(i, cnt2)
  194.         upd(pos[d[i]][0].x, pos[d[i]][0].y);
  195.        
  196.     forn(i, cnt2)
  197.         fore(j, i + 1, cnt2)
  198.             if ((a[d[i]].x > a[d[j]].x && a[d[i]].y < a[d[j]].y) || (a[d[i]].x < a[d[j]].x && a[d[i]].y > a[d[j]].y)){
  199.                 x1 = min(pos[d[i]][0].x, pos[d[j]][0].x);
  200.                 y1 = min(pos[d[i]][0].y, pos[d[j]][0].y);
  201.                 x2 = min(pos[d[i]][1].x, pos[d[j]][1].x);
  202.                 y2 = min(pos[d[i]][1].y, pos[d[j]][1].y);
  203.                
  204.                 cur = get(max(x1, x2), max(y1, y2)) -
  205.                       get(min(x1, x2) - 1, max(y1, y2)) -
  206.                       get(max(x1, x2), min(y1, y2) - 1) +
  207.                       get(min(x1, x2) - 1, min(y1, y2) - 1);
  208.                 res2 = max(cur, res2);
  209.                
  210.                 x1 = max(pos[d[i]][0].x, pos[d[j]][0].x);
  211.                 y1 = max(pos[d[i]][0].y, pos[d[j]][0].y);
  212.                 x2 = max(pos[d[i]][2].x, pos[d[j]][2].x);
  213.                 y2 = max(pos[d[i]][2].y, pos[d[j]][2].y);
  214.                
  215.                 cur = get(max(x1, x2), max(y1, y2)) -
  216.                       get(min(x1, x2) - 1, max(y1, y2)) -
  217.                       get(max(x1, x2), min(y1, y2) - 1) +
  218.                       get(min(x1, x2) - 1, min(y1, y2) - 1);
  219.                 res2 = max(cur, res2);
  220.             }
  221.             else{
  222.                 x1 = min(pos[d[i]][0].x, pos[d[j]][0].x);
  223.                 y1 = max(pos[d[i]][0].y, pos[d[j]][0].y);
  224.                 x2 = min(pos[d[i]][1].x, pos[d[j]][1].x);
  225.                 y2 = max(pos[d[i]][2].y, pos[d[j]][2].y);
  226.                
  227.                 cur = get(max(x1, x2), max(y1, y2)) -
  228.                       get(min(x1, x2) - 1, max(y1, y2)) -
  229.                       get(max(x1, x2), min(y1, y2) - 1) +
  230.                       get(min(x1, x2) - 1, min(y1, y2) - 1);
  231.                 res2 = max(cur, res2);
  232.                
  233.                 x1 = max(pos[d[i]][0].x, pos[d[j]][0].x);
  234.                 y1 = min(pos[d[i]][0].y, pos[d[j]][0].y);
  235.                 x2 = max(pos[d[i]][2].x, pos[d[j]][2].x);
  236.                 y2 = min(pos[d[i]][1].y, pos[d[j]][1].y);
  237.                
  238.                 cur = get(max(x1, x2), max(y1, y2)) -
  239.                       get(min(x1, x2) - 1, max(y1, y2)) -
  240.                       get(max(x1, x2), min(y1, y2) - 1) +
  241.                       get(min(x1, x2) - 1, min(y1, y2) - 1);
  242.                 res2 = max(cur, res2);
  243.             }
  244.        
  245.     forn(i, cnt2){
  246.         x1 = pos[d[i]][0].x;
  247.         y1 = pos[d[i]][0].y;
  248.         forn(j, 4){
  249.             x2 = pos[d[i]][dt[j].x > 0 ? 1 : 2].x;
  250.             y2 = pos[d[i]][dt[j].y > 0 ? 1 : 2].y;
  251.            
  252.             cur = get(max(x1, x2), max(y1, y2)) -
  253.                   get(min(x1, x2) - 1, max(y1, y2)) -
  254.                   get(max(x1, x2), min(y1, y2) - 1) +
  255.                   get(min(x1, x2) - 1, min(y1, y2) - 1);
  256.             res2 = max(res2, cur);
  257.         }
  258.     }
  259.        
  260.     return res1 + res2;
  261. }
  262.  
  263.  
  264. int check2(Line l){
  265.     int cnt1 = 0, cnt2 = 0;
  266.     forn(i, n)
  267.         if (l.A * a[i].x + l.B * a[i].y + l.C < -EPS)
  268.             b[cnt1++] = i;
  269.         else
  270.             d[cnt2++] = i;
  271.            
  272.     /*forn(i, cnt1)
  273.         printf("[%d %d] ", a[b[i]].x, a[b[i]].y);
  274.     printf("\n");
  275.    
  276.     forn(i, cnt2)
  277.         printf("[%d %d] ", a[d[i]].x, a[d[i]].y);
  278.     printf("\n\n");*/
  279.    
  280.     memset(f, 0, sizeof(f));
  281.  
  282.     forn(i, cnt1)
  283.         upd(pos[b[i]][0].x, pos[b[i]][0].y);
  284.    
  285.     int res1 = 0, res2 = 0;
  286.    
  287.     int x1, x2, y1, y2;
  288.     int cur;
  289.     forn(i, cnt1)
  290.         fore(j, i + 1, cnt1)
  291.             if ((a[b[i]].x > a[b[j]].x && a[b[i]].y < a[b[j]].y) || (a[b[i]].x < a[b[j]].x && a[b[i]].y > a[b[j]].y)){
  292.                 x1 = min(pos[b[i]][0].x, pos[b[j]][0].x);
  293.                 y1 = min(pos[b[i]][0].y, pos[b[j]][0].y);
  294.                 x2 = min(pos[b[i]][1].x, pos[b[j]][1].x);
  295.                 y2 = min(pos[b[i]][1].y, pos[b[j]][1].y);
  296.                
  297.                 cur = get(x2, y2) - get(x1 - 1, y2) - get(x2, y1 - 1) + get(x1 - 1, y1 - 1);
  298.                 res1 = max(cur, res1);
  299.                
  300.                 x1 = max(pos[b[i]][0].x, pos[b[j]][0].x);
  301.                 y1 = max(pos[b[i]][0].y, pos[b[j]][0].y);
  302.                 x2 = max(pos[b[i]][2].x, pos[b[j]][2].x);
  303.                 y2 = max(pos[b[i]][2].y, pos[b[j]][2].y);
  304.                
  305.                 cur = get(x1, y1) - get(x2 - 1, y1) - get(x1, y2 - 1) + get(x2 - 1, y2 - 1);
  306.                 res1 = max(cur, res1);
  307.             }
  308.             else{
  309.                 x1 = min(pos[b[i]][0].x, pos[b[j]][0].x);
  310.                 y1 = max(pos[b[i]][0].y, pos[b[j]][0].y);
  311.                 x2 = min(pos[b[i]][1].x, pos[b[j]][1].x);
  312.                 y2 = max(pos[b[i]][2].y, pos[b[j]][2].y);
  313.                
  314.                 cur = get(x2, y1) - get(x1 - 1, y1) - get(x2, y2 - 1) + get(x1 - 1, y2 - 1);
  315.                 res1 = max(cur, res1);
  316.                
  317.                 x1 = max(pos[b[i]][0].x, pos[b[j]][0].x);
  318.                 y1 = min(pos[b[i]][0].y, pos[b[j]][0].y);
  319.                 x2 = max(pos[b[i]][2].x, pos[b[j]][2].x);
  320.                 y2 = min(pos[b[i]][1].y, pos[b[j]][1].y);
  321.                
  322.                 cur = get(x1, y2) - get(x2 - 1, y2) - get(x1, y1 - 1) + get(x2 - 1, y1 - 1);
  323.                 res1 = max(cur, res1);
  324.             }
  325.            
  326.     forn(i, cnt1){
  327.         x1 = pos[b[i]][0].x;
  328.         y1 = pos[b[i]][0].y;
  329.         forn(j, 4){
  330.             x2 = pos[b[i]][dt[j].x > 0 ? 1 : 2].x;
  331.             y2 = pos[b[i]][dt[j].y > 0 ? 1 : 2].y;
  332.            
  333.             cur = get(max(x1, x2), max(y1, y2)) -
  334.                   get(min(x1, x2) - 1, max(y1, y2)) -
  335.                   get(max(x1, x2), min(y1, y2) - 1) +
  336.                   get(min(x1, x2) - 1, min(y1, y2) - 1);
  337.             res1 = max(res1, cur);
  338.         }
  339.     }
  340.        
  341.     memset(f, 0, sizeof(f));
  342.  
  343.     forn(i, cnt2)
  344.         upd(pos[d[i]][0].x, pos[d[i]][0].y);
  345.        
  346.     forn(i, cnt2)
  347.         fore(j, i + 1, cnt2)
  348.             if ((a[d[i]].x > a[d[j]].x && a[d[i]].y < a[d[j]].y) || (a[d[i]].x < a[d[j]].x && a[d[i]].y > a[d[j]].y)){
  349.                 x1 = min(pos[d[i]][0].x, pos[d[j]][0].x);
  350.                 y1 = min(pos[d[i]][0].y, pos[d[j]][0].y);
  351.                 x2 = min(pos[d[i]][1].x, pos[d[j]][1].x);
  352.                 y2 = min(pos[d[i]][1].y, pos[d[j]][1].y);
  353.                
  354.                 cur = get(max(x1, x2), max(y1, y2)) -
  355.                       get(min(x1, x2) - 1, max(y1, y2)) -
  356.                       get(max(x1, x2), min(y1, y2) - 1) +
  357.                       get(min(x1, x2) - 1, min(y1, y2) - 1);
  358.                 res2 = max(cur, res2);
  359.                
  360.                 x1 = max(pos[d[i]][0].x, pos[d[j]][0].x);
  361.                 y1 = max(pos[d[i]][0].y, pos[d[j]][0].y);
  362.                 x2 = max(pos[d[i]][2].x, pos[d[j]][2].x);
  363.                 y2 = max(pos[d[i]][2].y, pos[d[j]][2].y);
  364.                
  365.                 cur = get(max(x1, x2), max(y1, y2)) -
  366.                       get(min(x1, x2) - 1, max(y1, y2)) -
  367.                       get(max(x1, x2), min(y1, y2) - 1) +
  368.                       get(min(x1, x2) - 1, min(y1, y2) - 1);
  369.                 res2 = max(cur, res2);
  370.             }
  371.             else{
  372.                 x1 = min(pos[d[i]][0].x, pos[d[j]][0].x);
  373.                 y1 = max(pos[d[i]][0].y, pos[d[j]][0].y);
  374.                 x2 = min(pos[d[i]][1].x, pos[d[j]][1].x);
  375.                 y2 = max(pos[d[i]][2].y, pos[d[j]][2].y);
  376.                
  377.                 cur = get(max(x1, x2), max(y1, y2)) -
  378.                       get(min(x1, x2) - 1, max(y1, y2)) -
  379.                       get(max(x1, x2), min(y1, y2) - 1) +
  380.                       get(min(x1, x2) - 1, min(y1, y2) - 1);
  381.                 res2 = max(cur, res2);
  382.                
  383.                 x1 = max(pos[d[i]][0].x, pos[d[j]][0].x);
  384.                 y1 = min(pos[d[i]][0].y, pos[d[j]][0].y);
  385.                 x2 = max(pos[d[i]][2].x, pos[d[j]][2].x);
  386.                 y2 = min(pos[d[i]][1].y, pos[d[j]][1].y);
  387.                
  388.                 cur = get(max(x1, x2), max(y1, y2)) -
  389.                       get(min(x1, x2) - 1, max(y1, y2)) -
  390.                       get(max(x1, x2), min(y1, y2) - 1) +
  391.                       get(min(x1, x2) - 1, min(y1, y2) - 1);
  392.                 res2 = max(cur, res2);
  393.             }
  394.        
  395.     forn(i, cnt2){
  396.         x1 = pos[d[i]][0].x;
  397.         y1 = pos[d[i]][0].y;
  398.         forn(j, 4){
  399.             x2 = pos[d[i]][dt[j].x > 0 ? 1 : 2].x;
  400.             y2 = pos[d[i]][dt[j].y > 0 ? 1 : 2].y;
  401.            
  402.             cur = get(max(x1, x2), max(y1, y2)) -
  403.                   get(min(x1, x2) - 1, max(y1, y2)) -
  404.                   get(max(x1, x2), min(y1, y2) - 1) +
  405.                   get(min(x1, x2) - 1, min(y1, y2) - 1);
  406.             res2 = max(res2, cur);
  407.         }
  408.     }
  409.        
  410.     return res1 + res2;
  411. }
  412.  
  413.  
  414. void solve(int num){
  415.     int ans = (n == 1 ? 1 : 2);
  416.    
  417.     cx = cy = vector<int>();
  418.    
  419.     forn(i, n){
  420.         cx.pb(a[i].x);
  421.         cx.pb(a[i].x + R);
  422.         cx.pb(a[i].x - R);
  423.         cy.pb(a[i].y);
  424.         cy.pb(a[i].y + R);
  425.         cy.pb(a[i].y - R);
  426.     }
  427.    
  428.     sort(all(cx));
  429.     cx.resize(unique(all(cx)) - cx.begin());
  430.     sort(all(cy));
  431.     cy.resize(unique(all(cy)) - cy.begin());
  432.    
  433.     forn(i, n){
  434.         pos[i][0] = mp(lower_bound(all(cx), a[i].x) - cx.begin(), lower_bound(all(cy), a[i].y) - cy.begin());
  435.         pos[i][1] = mp(lower_bound(all(cx), a[i].x + R) - cx.begin(), lower_bound(all(cy), a[i].y + R) - cy.begin());
  436.         pos[i][2] = mp(lower_bound(all(cx), a[i].x - R) - cx.begin(), lower_bound(all(cy), a[i].y - R) - cy.begin());
  437.     }
  438.    
  439.     /*forn(i, n)
  440.         ans = max(ans, check(Circle(a[i])));
  441.     forn(i, n)
  442.         fore(j, i + 1, n)
  443.             ans = max(ans, check(Circle(a[i], a[j])));
  444.     forn(i, n)
  445.         fore(j, i + 1, n){
  446.             Line l = Line(a[i], a[j]);
  447.             fore(k, j + 1, n)
  448.                 if (!isOn(a[k], l))
  449.                     ans = max(ans, check(Circle(a[i], a[j], a[k])));
  450.         }*/
  451.        
  452.     forn(i, n)
  453.         fore(j, i + 1, n){
  454.             ans = max(ans, check1(Line(a[i], a[j])));
  455.             ans = max(ans, check2(Line(a[i], a[j])));
  456.         }
  457.        
  458.     printf("Case #%d: ", num);
  459.     printf("%d\n", ans);
  460. }
  461.  
  462.  
  463. int main(){
  464.     #ifdef _DEBUG
  465.         freopen("fighting_the_zombies.txt", "r", stdin);
  466.     #endif
  467.     int n;
  468.     scanf("%d", &n);
  469.     forn(i, n){
  470.         read();
  471.         solve(i + 1);
  472.     }
  473.     return 0;
  474. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!