이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |