제출 #538398

#제출 시각아이디문제언어결과실행 시간메모리
538398SortingThe Forest of Fangorn (CEOI14_fangorn)C++17
10 / 100
3095 ms340 KiB
#include <bits/stdc++.h> using namespace std; typedef long double ld; typedef long long ll; template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; } template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; } #define all(x) (x).begin(), (x).end() const ll N = 2000 + 3; const ll C = 1e4 + 3; const ll INF = 1e9; ll n, c, w, h; ll x, y; pair<ll, ll> cp[C], tp[N]; ll orient(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3){ return x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2; } ll sign(ll x){ return (x == 0) ? 0 : ((x > 0) ? 1 : -1); } bool on_line(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3){ if(orient(x1, y1, x2, y2, x3, y3)) return false; return min(x1, x2) <= x3 && x3 <= max(x1, x2) && min(y1, y2) <= y3 && y3 <= max(y1, y2); } bool intersectLine(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3, ll x4, ll y4){ ll a1 = sign(orient(x1, y1, x2, y2, x3, y3)); ll a2 = sign(orient(x1, y1, x2, y2, x4, y4)); ll a3 = sign(orient(x3, y3, x4, y4, x1, y1)); ll a4 = sign(orient(x3, y3, x4, y4, x2, y2)); return (a3 * a4) <= 0; } bool intersectSegments(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3, ll x4, ll y4){ ll a1 = sign(orient(x1, y1, x2, y2, x3, y3)); ll a2 = sign(orient(x1, y1, x2, y2, x4, y4)); ll a3 = sign(orient(x3, y3, x4, y4, x1, y1)); ll a4 = sign(orient(x3, y3, x4, y4, x2, y2)); if(on_line(x1, y1, x2, y2, x3, y3) && on_line(x1, y1, x2, y2, x4, y4)) return true; if(on_line(x3, y3, x4, y4, x1, y1) && on_line(x3, y3, x4, y4, x2, y2)) return true; if(!a1 || !a2 || !a3 || !a4) return false; if(a1 != a2 && a3 != a4) return true; return false; } bool check(ll x1, ll y1, ll x2, ll y2){ for(int i = 0; i < n; ++i){ for(int j = i + 1; j < n; ++j){ bool in1 = intersectSegments(x1, y1, x2, y2, tp[i].first, tp[i].second, tp[j].first, tp[j].second); if(intersectLine(x1, y1, x2, y2, tp[i].first, tp[i].second, tp[j].first, tp[j].second)){ if(!in1){ return false; } } } } return true; } bool check2(ll x, ll y){ for(int i = 0; i < n; ++i){ for(int j = i + 1; j < n; ++j){ if(orient(tp[i].first, tp[i].second, tp[j].first, tp[j].second, x, y) == 0){ if(!on_line(tp[i].first, tp[i].second, tp[j].first, tp[j].second, x, y)) return false; } } } return true; } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cin >> w >> h >> x >> y; cin >> c; for(int i = 0; i < c; ++i){ cin >> cp[i].first >> cp[i].second; } cin >> n; for(int i = 0; i < n; ++i){ cin >> tp[i].first >> tp[i].second; } ll midx = 0, midy = 0; for(int i = 0; i < n; ++i){ midx += tp[i].first; midy += tp[i].second; } midx /= n; midy /= n; vector<int> ans; for(int i = 0; i < c; ++i){ if(!check2(cp[i].first, cp[i].second)) continue; if(check(x, y, cp[i].first, cp[i].second)) ans.push_back(i + 1); else if(check(x, y, midx, midy) && check(midx, midy, cp[i].first, cp[i].second)) ans.push_back(i + 1); } cout << ans.size() << "\n"; for(int x: ans) cout << x << " "; cout << "\n"; }

컴파일 시 표준 에러 (stderr) 메시지

fangorn.cpp: In function 'bool intersectLine(ll, ll, ll, ll, ll, ll, ll, ll)':
fangorn.cpp:33:8: warning: unused variable 'a1' [-Wunused-variable]
   33 |     ll a1 = sign(orient(x1, y1, x2, y2, x3, y3));
      |        ^~
fangorn.cpp:34:8: warning: unused variable 'a2' [-Wunused-variable]
   34 |     ll a2 = sign(orient(x1, y1, x2, y2, x4, y4));
      |        ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...