Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define pub push_back
- #define ll long long
- #define mp make_pair
- #define all(a) a.begin(), a.end()
- using namespace std;
- struct point{
- ll x, y, num;
- point() {}
- point(ll x1, ll y1) { x = x1; y = y1; }
- point operator+ (const point nxt) const { return point(x + nxt.x, y + nxt.y); }
- point operator- (const point nxt) const { return point(x - nxt.x, y - nxt.y); }
- ll operator% (const point nxt) const { return x * nxt.y - y * nxt.x; }
- ll operator* (const point nxt) const { return x * nxt.x + y * nxt.y; }
- bool operator< (const point nxt) const { return mp(x, y) < mp(nxt.x, nxt.y); }
- bool operator!= (const point nxt) const { return mp(x, y) != mp(nxt.x, nxt.y); }
- };
- ll plTr(point a, point b, point c){
- return abs((a % b) + (b % c) + (c % a));
- }
- bool inTr(point t, point a, point b, point c){
- return plTr(a, b, c) == plTr(t, a, b) + plTr(t, a, c) + plTr(t, c, b);
- }
- int n, q;
- point a[5007];
- vector<point> convex(vector<point> a){
- sort(all(a));
- vector<point> t, q;
- for (int i = 0; i < a.size(); i++){
- 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();
- t.pub(a[i]);
- 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();
- q.pub(a[i]);
- }
- for (int i = (int)q.size() - 2; i >= 1; i--) t.pub(q[i]);
- return t;
- }
- bool ask(point a, point b, point c){
- cout << "? 3 " << a.num + 1 << ' ' << b.num + 1 << ' ' << c.num + 1 << "\n";
- cout.flush();
- string s;
- cin >> s;
- return (s == "Yes");
- }
- void prAns(point a, point b, point c){
- cout << "! 3 " << a.num + 1 << ' ' << b.num + 1 << ' ' << c.num + 1 << "\n";
- cout.flush();
- }
- vector<point> tt;
- vector<point> dd;
- void go(point a, point b, point c){
- if (tt.size() == 0){
- prAns(a, b, c);
- return;
- }
- int uk = (int)tt.size() / 2;
- dd.clear();
- if (ask(a, b, tt[uk])){
- for (int i = 0; i < tt.size(); i++) if (i != uk && inTr(tt[i], a, b, tt[uk])) dd.pub(tt[i]);
- swap(tt, dd);
- go(a, b, dd[uk]);
- return;
- }
- if (ask(a, c, tt[uk])){
- for (int i = 0; i < tt.size(); i++) if (i != uk && inTr(tt[i], a, c, tt[uk])) dd.pub(tt[i]);
- swap(tt, dd);
- go(a, c, dd[uk]);
- return;
- }
- if (ask(c, b, tt[uk])){
- for (int i = 0; i < tt.size(); i++) if (i != uk && inTr(tt[i], c, b, tt[uk])) dd.pub(tt[i]);
- swap(tt, dd);
- go(c, b, dd[uk]);
- return;
- }
- }
- vector<point> t, d;
- bool askk(int x){
- cout << "? " << x + 1 << ' ';
- for (int i = 0; i <= x; i++){
- cout << d[i].num + 1 << ' ';
- }
- cout << "\n";
- cout.flush();
- string s;
- cin >> s;
- return (s == "Yes");
- }
- const bool is_testing = 0;
- int main(){
- srand(123);
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- if (is_testing){
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- } else {
- }
- cin >> n;
- for (int i = 0; i < n; i++) cin >> a[i].x >> a[i].y, a[i].num = i;
- for (int i = 0; i < n; i++) t.pub(a[i]);
- t = convex(t);
- int uk = 0;
- 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;
- for (int i = 0; i < t.size(); i++){
- d.pub(t[uk++]);
- if (uk == t.size()) uk = 0;
- }
- cin >> q;
- while(q--){
- uk = 1;
- if (d.size() > 3){
- int l = 0, r = (int)d.size() - 2;
- while(l + 1 < r){
- int m = (l + r) >> 1;
- if (askk(m + 1))
- r = m;
- else
- l = m;
- }
- uk = r;
- }
- tt.clear();
- sort(all(tt));
- 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]);
- go(d[0], d[uk], d[uk + 1]);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement