제출 #64795

#제출 시각아이디문제언어결과실행 시간메모리
64795bazsi700The Forest of Fangorn (CEOI14_fangorn)C++14
100 / 100
317 ms1308 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define C complex<ll> #define X real() #define Y imag() ll w,h,n,c; C g; C camp[10005]; C tree[10005]; bool can[15]; int sign(ll x) { if(x > 0) { return 1; } else if(x == 0) { return 0; } else { return -1; } } ll cross(C a, C b) { //-1 bal, 0 egyenes, 1 jobb A hoz képest a B return sign(((a*conj(b)).Y)); } bool isbadv[10005]; int leftest[10005]; int rightest[10005]; int leftof[10005]; int rightof[10005]; int main() { ios::sync_with_stdio(false); cin.tie(0); ll gx,gy; cin >> w >> h >> gx >> gy >> c; g = {gx,gy}; for(int i = 0; i < c; i++) { ll x,y; cin >> x >> y; camp[i] = {x,y}; } cin >> n; for(int i = 0; i < n; i++) { ll x,y; cin >> x >> y; tree[i] = {x,y}; } for(int i = 0; i < n; i++) { bool bad = false; int fix = (i == 0 ? 1 : 0); for(int j = 0; j < n; j++) { if(j == i || j == fix) { continue; } if(cross(tree[fix]-tree[i],tree[j]-tree[i]) > 0) { fix = j; } } for(int j = 0; j < n; j++) { if(j == i || j == fix) { continue; } if(cross(tree[fix]-tree[i],tree[j]-tree[i]) > 0) { bad = true; } } if(bad) { int left1 = -1; for(int x = 0; x < n; x++) { if(x == i) { continue; } if(cross(tree[i]-g,tree[x]-tree[i]) < 0) { if(left1 == -1 || cross(tree[x]-tree[i],tree[left1]-tree[i]) < 0) { left1 = x; } } } leftof[i] = left1; int right1 = -1; for(int x = 0; x < n; x++) { if(x == i) { continue; } if(cross(tree[i]-g,tree[x]-tree[i]) > 0) { if(right1 == -1 || cross(tree[x]-tree[i],tree[right1]-tree[i]) > 0) { right1 = x; } } } rightof[i] = right1; isbadv[i] = true; } else { leftest[i] = fix; } } for(int i = 0; i < n; i++) { if(isbadv[i]) { continue; } int fix = (i == 0 ? 1 : 0); for(int j = 0; j < n; j++) { if(j == i || j == fix) { continue; } if(cross(tree[fix]-tree[i],tree[j]-tree[i]) < 0) { fix = j; } } rightest[i] = fix; //cout << i << " " << leftest[i] << " " << rightest[i] << "a\n"; } vector<int> pr; for(int i = 0; i < c; i++) { bool good = true; /* for(int x = 0; x < n; x++) { for(int y = x+1; y < n; y++) { if(isbad[x][y]) { if(cross(tree[y]-tree[x],g-tree[x]) == -cross(tree[y]-tree[x],camp[i]-tree[x])) { good = false; } } } } // cout << good << "\n"; if(!good) { continue; }*/ for(int a2 = 0; a2 < n && good; a2++) { if(!isbadv[a2]) { int b1 = a2; int a1 = leftest[a2]; int b2 = rightest[a2]; if(b2 == a1 || b2 == a2) { continue; } if(cross(tree[a2]-tree[a1],camp[i]-tree[a1]) != -cross(tree[a2]-tree[a1],g-tree[a1]) && cross(tree[b2]-tree[b1],camp[i]-tree[b1]) != -cross(tree[b2]-tree[b1],g-tree[b1])) { continue; } if(cross(tree[a2]-tree[a1],tree[b2]-tree[a1]) == -cross(tree[a2]-tree[a1],camp[i]-tree[a1]) && cross(tree[b2]-tree[b1],tree[a1]-tree[b1]) == -cross(tree[b2]-tree[b1],camp[i]-tree[b1])) { good = false; // cout << a1 << " " << b1 << " " << b2 << endl; } if(cross(tree[a2]-tree[a1],tree[b2]-tree[a1]) == -cross(tree[a2]-tree[a1],g-tree[a1]) && cross(tree[b2]-tree[b1],tree[a1]-tree[b1]) == -cross(tree[b2]-tree[b1],g-tree[b1])) { good = false; // cout << a1 << " " << b1 << " " << b2 << endl; } } else { int left1 = leftof[a2]; int right1 = rightof[a2]; if(cross(tree[a2]-camp[i],tree[left1]-tree[a2]) > 0 || cross(tree[a2]-camp[i],tree[right1]-tree[a2]) < 0) { good = false; } // if(i == 2) { // cout << left1 << " " << left2 << endl; //} } } if(good) { pr.push_back(i+1); } } cout << pr.size() << "\n"; for(int el : pr) { cout << el << " "; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...