#include <bits/stdc++.h>
#define MP make_pair
#define F first
#define PB push_back
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int mod = (int)1e9 + 7;
const int maxn = 1e4 + 4;
const ll inf = 1e18;
pii p[maxn];
vector <int> v[maxn];
pii operator + (pii fi, pii se) {
return {fi.F + se.F, fi.S + se.S};
}
pii operator - (pii fi, pii se) {
return {fi.F - se.F, fi.S - se.S};
}
bool cmp (int fi, int se) {
if (p[fi].S == 0)
return 1;
if (p[se].S == 0)
return 0;
return p[fi].F / p[fi].S > p[se].F / p[se].S;
}
int cross(pii A, pii B, pii C){
pii AB;
pii AC;
AB.F = B.F - A.F;
AB.S = B.S - A.S;
AC.F = C.F - A.F;
AC.S = C.S - A.S;
int cross = AB.F * AC.S - AB.S * AC.F;
return cross;
}
bool isright (pii a, pii b, pii c) {
if (cross (a, b, c) > 0)
return 1;
return 0;
}
int n;
int district (int src, pii x) {
for (int i = 0; i < n - 1; i++){
pii AB = p[src] - p[v[src][i]];
pii AC = p[src] - p[v[src][(i + 1) % (n - 1)]];
if (isright (p[src], p[src] + AB, p[src] + AC)) {
if (isright (p[src], p[src] + AB, x) and !isright (p[src], p[src] + AC, x))
return i;
}
else {
if (isright (p[src], p[src] + AB, x) or !isright (p[src], p[src] + AC, x))
return i;
}
}
/* int lo = 0, hi = n;
while (hi - lo > 1) {
int mid = (hi + lo) >> 1;
pii AB = p[src] - p[v[src][0]];
pii AC = p[src] - p[v[src][mid]];
// cout << mid << " -> " << AB.F << " " << AB.S << " - " << AC.F << " " << AC.S << endl;
if (isright (p[src], p[src] + AB, p[src] + AC)) {
if (isright (p[src], p[src] + AB, x) and !isright (p[src], p[src] + AC, x)) {
hi = mid;
}
else {
lo = mid;
}
}
else {
if (isright (p[src], p[src] + AB, x) or !isright (p[src], p[src] + AC, x)) {
hi = mid;
}
else {
lo = mid;
}
}
}
return hi;
*/
}
bool isinsame (int src, pii fi, pii se) {
// cout << district (src, fi) << endl << district (src, se) << endl;
if (district (src, fi) == district (src, se))
return 1;
return 0;
}
pii c[maxn];
int main (){
ios_base::sync_with_stdio(false);
int w, h;
cin >> w >> h;
pii s;
cin >> s.F >> s.S;
int number_of_camps;
cin >> number_of_camps;
for (int i = 0; i < number_of_camps; i++)
cin >> c[i].F >> c[i].S;
cin >> n;
for (int i = 0; i < n; i++)
cin >> p[i].F >> p[i].S;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j)
continue;
v[i].PB (j);
p[j].F = p[i].F - p[j].F;
p[j].S = p[i].S - p[j].S;
}
sort (v[i].begin(), v[i].end(), cmp);
for (int j = 0; j < n; j++) {
if (j == i)
continue;
p[j].F -= p[i].F;
p[j].F *= -1;
p[j].S -= p[i].S;
p[j].S *= -1;
}
}
// for (auto it : v[3])
// cout << it << " ";
// cout << endl;
// isinsame (3, c[0], s);
// return 0;
vector <int> ans;
for (int i = 0; i < number_of_camps; i++) {
bool found = 0;
for (int j = 0; j < n; j++) {
// cout << i << " " << j << " -> " << isinsame (j, c[i], s) << endl;
if (!isinsame (j, c[i], s)) {
found = 1;
break;
}
}
if (!found)
ans.PB (i + 1);
}
cout << ans.size() << endl;
for (auto it : ans)
cout << it << " ";
cout << endl;
}
Compilation message
fangorn.cpp: In function 'int district(int, pii)':
fangorn.cpp:89:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
744 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
744 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
744 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
760 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
820 KB |
Output isn't correct |
| 7 |
Correct |
3 ms |
836 KB |
Output is correct |
| 8 |
Incorrect |
3 ms |
836 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
836 KB |
Output is correct |
| 2 |
Correct |
3 ms |
848 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
964 KB |
Output isn't correct |
| 4 |
Correct |
3 ms |
964 KB |
Output is correct |
| 5 |
Correct |
4 ms |
964 KB |
Output is correct |
| 6 |
Correct |
4 ms |
992 KB |
Output is correct |
| 7 |
Correct |
2 ms |
992 KB |
Output is correct |
| 8 |
Correct |
3 ms |
992 KB |
Output is correct |
| 9 |
Incorrect |
2 ms |
992 KB |
Output isn't correct |
| 10 |
Incorrect |
6 ms |
992 KB |
Output isn't correct |
| 11 |
Incorrect |
7 ms |
992 KB |
Output isn't correct |
| 12 |
Correct |
5 ms |
1048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
1048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
483 ms |
17168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
