Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //LiveArchive 3655 Onion Layers - TCBPG
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- #include <vector>
- using namespace std;
- #define forn(i, n) for(int i = 0; i < (int) (n); i++)
- #define forsn(i, s, n) for(int i = (s); i < (int) (n); i++)
- typedef long long tint;
- inline int sqr(int x){ return x*x; }
- int pcruz(int x1, int y1, int x2, int y2){ return x1*y2-x2*y1; }
- struct pto{
- int x,y;
- int n2(pto &p2) const { return sqr(x-p2.x) + sqr(y-p2.y); };
- pto(int u, int v){ x = u, y = v; };
- pto(){};
- } r;
- int area3(pto a, pto b, pto c){ return pcruz(b.x-a.x, b.y-a.y, c.x-a.x, c.y-a.y); }
- bool men2(const pto&p1, const pto&p2){
- return (p1.y == p2.y) ? (p1.x < p2.x) : (p1.y < p2.y);
- }
- bool orden(const pto & p1, const pto & p2){
- return (p1.x == p2.x) ? (p1.y < p2.y) : (p1.x < p2.x);
- }
- bool operator<(const pto &p1, const pto&p2){
- int ar = area3(r, p1, p2);
- return (ar == 0) ? (p1.n2(r) < p2.n2(r)) : ar>0;
- }
- bool operator==(const pto& p1, const pto & p2){
- return (p1.x == p2.x && p1.y == p2.y);
- }
- typedef vector<pto> VP;
- VP chull(VP & P){
- int n = P.size(), k = 0;
- vector<pto> H(2*n);
- // Sort Points lexicographically
- sort(P.begin(), P.end(), men2);
- // Build lower hull
- for (int i = 0; i < n; i++) {
- while (k >= 2 && area3(H[k-2], H[k-1], P[i]) < 0){
- k--;
- }
- H[k++] = P[i];
- }
- // Build upper hull
- for (int i = n-2, t = k+1; i >= 0; i--) {
- while (k >= t && area3(H[k-2], H[k-1], P[i]) < 0){
- k--;
- }
- H[k++] = P[i];
- }
- H.resize(k);
- return H;
- }
- int main(){
- #ifdef ACM
- freopen("test.in", "r", stdin);
- #endif
- int N; scanf("%d", &N);
- while(N != 0){
- int L = 0;
- VP v;
- forn(i, N){
- int x, y; scanf("%d %d", &x, &y);
- v.push_back(pto(x, y));
- }
- while(v.size() > 0){
- VP ch = chull(v);
- VP tmp(v.size());
- sort(ch.begin(), ch.end(), men2);
- sort(v.begin(), v.end(), men2);
- VP::iterator it = set_difference(v.begin(), v.end(), ch.begin(), ch.end(), tmp.begin(), men2);
- tmp.resize(it - tmp.begin());
- v.clear();
- v = tmp;
- L++;
- }
- if(L % 2 == 0) puts("Do not take this onion to the lab!"); else puts("Take this onion to the lab!");
- scanf("%d", &N);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment