#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=2005, maxm=1e4+5;
const double inf=2e18;
pair < int, int > d[maxn];
pair < int, int > q[maxm];
int n, m;
vector < double > kor[4]; // jednadzbe: x=0, y=0, x=w, y=h
vector < pair < double, int > > sw[4];
bool moze[maxm];
vector < int > sol;
pair < int, int > pos;
int w, h;
void radi(int x, int y){
double a, b, c;
int dx, dy;
dx=d[x].first-d[y].first;
dy=d[x].second-d[y].second;
a=-dy;
b=dx;
c=-a*d[x].first-b*d[x].second;
double sol1, sol2, sol3, sol4;
if(b==0){
sol1=-inf;
sol3=inf;
}
else{
sol1=-c/b;
sol3=(-c-a*w)/b;
}
if(a==0){
sol2=-inf;
sol4=inf;
}
else{
sol2=-c/a;
sol4=(-c-b*h)/a;
}
if(b==0){
if(d[x].second<d[y].second){
kor[0].push_back(sol1);
kor[2].push_back(sol1);
}
else{
kor[0].push_back(sol3);
kor[2].push_back(sol3);
}
}
else if(d[x].first<d[y].first){
kor[0].push_back(sol1);
}
else{
kor[2].push_back(sol3);
}
if(a==0){
if(d[x].first<d[y].first){
kor[1].push_back(sol2);
kor[3].push_back(sol2);
}
else{
kor[1].push_back(sol4);
kor[3].push_back(sol4);
}
}
else if(d[x].second<d[y].second){
kor[1].push_back(sol2);
}
else{
kor[3].push_back(sol4);
}
}
double ccw(pair < double, double > a, pair < double, double > b, pair < double, double > c){
return a.first*(b.second-c.second)+b.first*(c.second-a.second)+c.first*(a.second-b.second);
}
bool provjeri(pair < double, double > a, pair < double, double > b, pair < double, double > c, pair < double, double > x){
if(ccw(a, b, c)<0){
swap(b, c);
}
return ccw(a, b, x)>=0 && ccw(b, c, x)>=0 && ccw(c, a, x)>=0;
}
void rijesi(int x, int y){
sort(kor[y].begin(), kor[y].end());
pair < double, double > t1, t2;
if(y==0){
t1.first=0;
t2.first=0;
}
else if(y==1){
t1.second=0;
t2.second=0;
}
else if(y==2){
t1.first=w;
t2.first=w;
}
else{
t1.second=h;
t2.second=h;
}
int ind=-1;
for(int i=0; i<(int)kor[y].size()-1; i++){
if(y==0){
t1.second=kor[y][i];
t2.second=kor[y][i+1];
}
else if(y==1){
t1.first=kor[y][i];
t2.first=kor[y][i+1];
}
else if(y==2){
t1.second=kor[y][i];
t2.second=kor[y][i+1];
}
else{
t1.first=kor[y][i];
t2.first=kor[y][i+1];
}
if(provjeri(t1, t2, d[x], pos)){
ind=i;
break;
}
}
if(kor[y].size()>1){
sw[y].push_back({kor[y][0], 1});
sw[y].push_back({kor[y].back(), -1});
if(ind!=-1){
for(int i=0; i<m; i++){
if(moze[i] && !provjeri(t1, t2, d[x], q[i])){
moze[i]=0;
}
}
sw[y].push_back({kor[y][ind], -1});
sw[y].push_back({kor[y][ind+1], 1});
}
}
}
int main(){
scanf("%d%d", &w, &h);
scanf("%d%d", &pos.first, &pos.second);
scanf("%d", &m);
for(int i=0; i<m; i++){
moze[i]=1;
scanf("%d%d", &q[i].first, &q[i].second);
}
scanf("%d", &n);
for(int i=0; i<n; i++){
scanf("%d%d", &d[i].first, &d[i].second);
}
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(i==j){
continue;
}
radi(i, j);
}
for(int j=0; j<4; j++){
rijesi(i, j);
kor[j].clear();
}
}
for(int i=0; i<m; i++){
if(q[i].first==0){
sw[0].push_back({q[i].second, i+2});
}
else if(q[i].second==0){
sw[1].push_back({q[i].first, i+2});
}
else if(q[i].first==w){
sw[2].push_back({q[i].second, i+2});
}
else{
sw[3].push_back({q[i].first, i+2});
}
}
int val;
for(int i=0; i<4; i++){
sort(sw[i].begin(), sw[i].end());
val=0;
for(int j=0; j<(int)sw[i].size(); j++){
if(sw[i][j].second<2){
val+=sw[i][j].second;
}
else{
if(val || !moze[sw[i][j].second-2]){
continue;
}
sol.push_back(sw[i][j].second-1);
}
}
}
printf("%d\n", (int)sol.size());
sort(sol.begin(), sol.end());
for(int i=0; i<(int)sol.size(); i++){
printf("%d ", sol[i]);
}
printf("\n");
return 0;
}
Compilation message
fangorn.cpp: In function 'int main()':
fangorn.cpp:150:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
150 | scanf("%d%d", &w, &h);
| ~~~~~^~~~~~~~~~~~~~~~
fangorn.cpp:151:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
151 | scanf("%d%d", &pos.first, &pos.second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:152:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
152 | scanf("%d", &m);
| ~~~~~^~~~~~~~~~
fangorn.cpp:155:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
155 | scanf("%d%d", &q[i].first, &q[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:157:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
157 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
fangorn.cpp:159:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
159 | scanf("%d%d", &d[i].first, &d[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
0 ms |
204 KB |
Output is correct |
| 6 |
Correct |
0 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
1 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
2 ms |
332 KB |
Output is correct |
| 7 |
Correct |
0 ms |
204 KB |
Output is correct |
| 8 |
Correct |
0 ms |
204 KB |
Output is correct |
| 9 |
Correct |
1 ms |
204 KB |
Output is correct |
| 10 |
Correct |
5 ms |
332 KB |
Output is correct |
| 11 |
Correct |
7 ms |
332 KB |
Output is correct |
| 12 |
Correct |
5 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
147 ms |
508 KB |
Output is correct |
| 5 |
Correct |
31 ms |
340 KB |
Output is correct |
| 6 |
Correct |
630 ms |
792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
633 ms |
728 KB |
Output is correct |
| 2 |
Correct |
638 ms |
1104 KB |
Output is correct |
| 3 |
Correct |
667 ms |
1196 KB |
Output is correct |
| 4 |
Correct |
261 ms |
1088 KB |
Output is correct |
