-
-
Save rafaelgo2/359ebe7bbd78b2837399b7cb86714694 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
#define _ ios_base::sync_with_stdio(0);cin.tie(0); | |
using namespace std; | |
#define INF 1e9 | |
#define EPS 1e-4 | |
typedef int type; | |
typedef pair<type, type> point; | |
const point infPoint(INF, INF); | |
typedef pair<type, type> vec; | |
#define x first | |
#define y second | |
point operator*(type alpha, point p){ | |
return point(alpha*p.x, alpha*p.y); | |
} | |
point operator+(point l, point r){ | |
return point(l.x + r.x, l.y + r.y); | |
} | |
vec operator-(point l, point r){ //might be confusing | |
return vec(l.x - r.x, l.y - r.y); | |
} | |
type dot(vec p, vec q){ | |
return p.x*q.x + p.y*q.y; | |
} | |
double length(vec v){ | |
return hypot(v.x, v.y); | |
} | |
type cross(vec p, vec q){ | |
return p.x*q.y - p.y*q.x; | |
} | |
type operator*(vec p, vec q){ | |
return dot(p, q); | |
} | |
type operator^(vec p, vec q){ | |
return cross(p, q); | |
} | |
double operator~(vec v){ | |
return length(v); | |
} | |
void convex_hull(vector<point> &v, vector<point> &ans){ | |
if (v.size() < 3){ | |
ans = v; | |
if (ans.front() != ans.back()) ans.push_back(ans.front()); | |
return; | |
} | |
sort(v.begin(), v.end()); | |
static vector<point> cap; | |
cap.resize(0); | |
cap.push_back(v[0]), cap.push_back(v[1]); | |
for (int i = 2; i < v.size(); i++){ | |
while(cap.size() >= 2){ | |
int n = cap.size(); | |
if (((v[i] - cap[n-2])^(cap[n-1] - cap[n-2])) < 0) // <= exclude colinear points | |
cap.pop_back(); | |
else | |
break; | |
} | |
cap.push_back(v[i]); | |
} | |
static vector<point> cup; | |
cup.resize(0); | |
cup.push_back(v[0]), cup.push_back(v[1]); | |
for (int i = 2; i < v.size(); i++){ | |
while(cup.size() >= 2){ | |
int n = cup.size(); | |
if (((v[i] - cup[n-2])^(cup[n-1] - cup[n-2])) > 0) //>= exclude colinear points | |
cup.pop_back(); | |
else | |
break; | |
} | |
cup.push_back(v[i]); | |
} | |
ans.resize(0); | |
for (int i = 0; i < cap.size(); i++) | |
ans.push_back(cap[i]); | |
for (int i = cup.size() - 2; i >= 0; i--) | |
ans.push_back(cup[i]); | |
} | |
int main(){ _ | |
int n; | |
vector<point> v; | |
vector<point> ch; | |
while (true){ | |
cin >> n; | |
if (n == 0) break; | |
v.resize(n); | |
for (int i = 0; i < n; i++) | |
cin >> v[i].x >> v[i].y; | |
int count = 0; | |
while (v.size() > 0){ | |
convex_hull(v, ch); | |
set<point> tmp(v.begin(), v.end()); | |
for (point p : ch) | |
if (tmp.count(p)) tmp.erase(p); | |
v = vector<point>(tmp.begin(), tmp.end()); | |
bool colinear = true; | |
int sz = ch.size(); | |
for (int i = 2; i < sz; i++){ | |
colinear &= | |
((ch[i] - ch[i-1])^(ch[i-1] - ch[i-2])) == 0; | |
} | |
if (colinear) | |
break; | |
count++; | |
} | |
if (count % 2 == 0) | |
cout << "Do not take this onion to the lab!" << endl; | |
else | |
cout << "Take this onion to the lab!" << endl; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment