Advertisement
Guest User

Untitled

a guest
Apr 28th, 2017
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.07 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define pub push_back
  4. #define ll long long
  5. #define mp make_pair
  6. #define all(a) a.begin(), a.end()
  7.  
  8. using namespace std;
  9.  
  10. struct point{
  11.     ll x, y, num;
  12.     point() {}
  13.     point(ll x1, ll y1) { x = x1; y = y1; }
  14.     point operator+ (const point nxt) const { return point(x + nxt.x, y + nxt.y); }
  15.     point operator- (const point nxt) const { return point(x - nxt.x, y - nxt.y); }
  16.     ll operator% (const point nxt) const { return x * nxt.y - y * nxt.x; }
  17.     ll operator* (const point nxt) const { return x * nxt.x + y * nxt.y; }
  18.     bool operator< (const point nxt) const { return mp(x, y) < mp(nxt.x, nxt.y); }
  19.     bool operator!= (const point nxt) const { return mp(x, y) != mp(nxt.x, nxt.y); }
  20. };
  21.  
  22. ll plTr(point a, point b, point c){
  23.     return abs((a % b) + (b % c) + (c % a));
  24. }
  25.  
  26. bool inTr(point t, point a, point b, point c){
  27.     return plTr(a, b, c) == plTr(t, a, b) + plTr(t, a, c) + plTr(t, c, b);
  28. }
  29.  
  30. int n, q;
  31. point a[5007];
  32.  
  33. vector<point> convex(vector<point> a){
  34.     sort(all(a));
  35.     vector<point> t, q;
  36.     for (int i = 0; i < a.size(); i++){
  37.         while(t.size() >= 2 && ((a[i] - t[(int)t.size() - 2]) % (t[(int)t.size() - 1] - t[(int)t.size() - 2])) <= 0) t.pop_back();
  38.         t.pub(a[i]);
  39.         while(q.size() >= 2 && ((a[i] - q[(int)q.size() - 2]) % (q[(int)q.size() - 1] - q[(int)q.size() - 2])) >= 0) q.pop_back();
  40.         q.pub(a[i]);
  41.     }
  42.     for (int i = (int)q.size() - 2; i >= 1; i--) t.pub(q[i]);
  43.     return t;
  44. }
  45.  
  46. bool ask(point a, point b, point c){
  47.     cout << "? 3 " << a.num + 1 << ' ' << b.num + 1 << ' ' << c.num + 1 << "\n";
  48.     cout.flush();
  49.     string s;
  50.     cin >> s;
  51.     return (s == "Yes");
  52. }
  53.  
  54. void prAns(point a, point b, point c){
  55.     cout << "! 3 " << a.num + 1 << ' ' << b.num + 1 << ' ' << c.num + 1 << "\n";
  56.     cout.flush();
  57. }
  58.  
  59. vector<point> tt;
  60. vector<point> dd;
  61.  
  62. void go(point a, point b, point c){
  63.     if (tt.size() == 0){
  64.         prAns(a, b, c);
  65.         return;
  66.     }
  67.     int uk = (int)tt.size() / 2;
  68.     dd.clear();
  69.     if (ask(a, b, tt[uk])){
  70.         for (int i = 0; i < tt.size(); i++) if (i != uk && inTr(tt[i], a, b, tt[uk])) dd.pub(tt[i]);
  71.         swap(tt, dd);
  72.         go(a, b, dd[uk]);
  73.         return;
  74.     }
  75.     if (ask(a, c, tt[uk])){
  76.         for (int i = 0; i < tt.size(); i++) if (i != uk && inTr(tt[i], a, c, tt[uk])) dd.pub(tt[i]);
  77.         swap(tt, dd);
  78.         go(a, c, dd[uk]);
  79.         return;
  80.     }
  81.     if (ask(c, b, tt[uk])){
  82.         for (int i = 0; i < tt.size(); i++) if (i != uk && inTr(tt[i], c, b, tt[uk])) dd.pub(tt[i]);
  83.         swap(tt, dd);
  84.         go(c, b, dd[uk]);
  85.         return;
  86.     }
  87. }
  88.  
  89. vector<point> t, d;
  90.  
  91. bool askk(int x){
  92.     cout << "? " << x + 1 << ' ';
  93.     for (int i = 0; i <= x; i++){
  94.         cout << d[i].num + 1 << ' ';
  95.     }
  96.     cout << "\n";
  97.     cout.flush();
  98.     string s;
  99.     cin >> s;
  100.     return (s == "Yes");
  101. }
  102.  
  103. const bool is_testing = 0;
  104. int main(){
  105.     srand(123);
  106.     ios_base::sync_with_stdio(0);
  107.     cin.tie(0);
  108.     if (is_testing){
  109.         freopen("input.txt", "r", stdin);
  110.         freopen("output.txt", "w", stdout);
  111.     } else {
  112.  
  113.     }
  114.     cin >> n;
  115.     for (int i = 0; i < n; i++) cin >> a[i].x >> a[i].y, a[i].num = i;
  116.     for (int i = 0; i < n; i++) t.pub(a[i]);
  117.     t = convex(t);
  118.     int uk = 0;
  119.     for (int i = 0; i < t.size(); i++) if (t[i].y < t[uk].y || (t[i].y == t[uk].y && t[i].x < t[uk].y)) uk = i;
  120.     for (int i = 0; i < t.size(); i++){
  121.         d.pub(t[uk++]);
  122.         if (uk == t.size()) uk = 0;
  123.     }
  124.     cin >> q;
  125.     while(q--){
  126.         uk = 1;
  127.         if (d.size() > 3){
  128.             int l = 0, r = (int)d.size() - 2;
  129.             while(l + 1 < r){
  130.                 int m = (l + r) >> 1;
  131.                 if (askk(m + 1))
  132.                     r = m;
  133.                 else
  134.                     l = m;
  135.             }
  136.             uk = r;
  137.         }
  138.         tt.clear();
  139.         sort(all(tt));
  140.         for (int i = 0; i < n; i++) if (a[i] != d[0] && a[i] != d[uk] && a[i] != d[uk + 1] && inTr(a[i], d[0], d[uk], d[uk + 1])) tt.pub(a[i]);
  141.         go(d[0], d[uk], d[uk + 1]);
  142.     }
  143. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement