QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#104031 | #523. 部落战争 | zaneyu | 0 | 119ms | 10980kb | C++23 | 6.5kb | 2023-05-08 12:02:23 | 2023-05-08 12:02:24 |
Judging History
answer
/*input
4 4 3
0 0
1 0
0 1
1 1
-1 0
0 3
0 2
0 -1
0 0
2 3
0 -1
*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
//#pragma GCC target("avx2")
//order_of_key #of elements less than x
// find_by_order kth element
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll maxn=4e5+5;
const ll maxlg=__lg(maxn)+2;
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
const ld PI=acos(-1);
const ld eps=1e-4;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
out<<P.f<<' '<<P.s;
return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
REP(i,sz(V)) out<<V[i]<<((i!=sz(V)-1)?",":"");
return out;
}
ll mult(ll a,ll b){
return a*b%MOD;
}
ll mypow(ll a,ll b){
a%=MOD;
if(a==0) return 0;
if(b<=0) return 1;
ll res=1LL;
while(b){
if(b&1) res=(res*a)%MOD;
a=(a*a)%MOD;
b>>=1;
}
return res;
}
struct pt{
long long x, y;
pt() {}
pt(long long _x, long long _y) : x(_x), y(_y) {}
pt operator+(const pt &p) const { return pt(x + p.x, y + p.y); }
pt operator-(const pt &p) const { return pt(x - p.x, y - p.y); }
long long cross(const pt &p) const { return x * p.y - y * p.x; }
long long dot(const pt &p) const { return x * p.x + y * p.y; }
long long cross(const pt &a, const pt &b) const { return (a - *this).cross(b - *this); }
long long dot(const pt &a, const pt &b) const { return (a - *this).dot(b - *this); }
long long sqrLen() const { return this->dot(*this); }
};
void reorder_polygon(vector<pt> & P){
size_t pos = 0;
for(size_t i = 1; i < P.size(); i++){
if(P[i].y < P[pos].y || (P[i].y == P[pos].y && P[i].x < P[pos].x))
pos = i;
}
rotate(P.begin(), P.begin() + pos, P.end());
}
vector<pt> minkowski(vector<pt> P, vector<pt> Q){
// the first vertex must be the lowest
reorder_polygon(P);
reorder_polygon(Q);
// we must ensure cyclic indexing
P.push_back(P[0]);
P.push_back(P[1]);
Q.push_back(Q[0]);
Q.push_back(Q[1]);
// main part
vector<pt> result;
size_t i = 0, j = 0;
while(i < P.size() - 2 and j < Q.size() - 2){
result.push_back(P[i] + Q[j]);
auto cross = (P[i + 1] - P[i]).cross(Q[j + 1] - Q[j]);
if(cross >= 0)
++i;
if(cross <= 0)
++j;
}
while(i<sz(P)-2) result.pb(P[i++]+Q[j]);
while(j<sz(P)-2) result.pb(P[i]+Q[j++]);
return result;
}
int orientation(pt a, pt b, pt c) {
double v = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
if (v < 0) return -1; // clockwise
if (v > 0) return +1; // counter-clockwise
return 0;
}
bool cw(pt a, pt b, pt c, bool include_collinear) {
int o = orientation(a, b, c);
return o < 0 || (include_collinear && o == 0);
}
bool collinear(pt a, pt b, pt c) { return orientation(a, b, c) == 0; }
void convex_hull(vector<pt>& a, bool include_collinear = false) {
pt p0 = *min_element(a.begin(), a.end(), [](pt a, pt b) {
return make_pair(a.y, a.x) < make_pair(b.y, b.x);
});
sort(a.begin(), a.end(), [&p0](const pt& a, const pt& b) {
int o = orientation(p0, a, b);
if (o == 0)
return (p0.x-a.x)*(p0.x-a.x) + (p0.y-a.y)*(p0.y-a.y)
< (p0.x-b.x)*(p0.x-b.x) + (p0.y-b.y)*(p0.y-b.y);
return o < 0;
});
if (include_collinear) {
int i = (int)a.size()-1;
while (i >= 0 && collinear(p0, a[i], a.back())) i--;
reverse(a.begin()+i+1, a.end());
}
vector<pt> st;
for (int i = 0; i < (int)a.size(); i++) {
while (st.size() > 1 && !cw(st[st.size()-2], st.back(), a[i], include_collinear))
st.pop_back();
st.push_back(a[i]);
}
a = st;
}
bool lexComp(const pt &l, const pt &r) {
return l.x < r.x || (l.x == r.x && l.y < r.y);
}
int sgn(long long val) { return val > 0 ? 1 : (val == 0 ? 0 : -1); }
vector<pt> seq;
pt translation;
int n;
bool pointInTriangle(pt a, pt b, pt c, pt point) {
long long s1 = abs(a.cross(b, c));
long long s2 = abs(point.cross(a, b)) + abs(point.cross(b, c)) + abs(point.cross(c, a));
return s1 == s2;
}
void prepare(vector<pt> &points) {
n = points.size();
int pos = 0;
for (int i = 1; i < n; i++) {
if (lexComp(points[i], points[pos]))
pos = i;
}
rotate(points.begin(), points.begin() + pos, points.end());
n--;
seq.resize(n);
for (int i = 0; i < n; i++)
seq[i] = points[i + 1] - points[0];
translation = points[0];
}
bool pointInConvexPolygon(pt point) {
point = point - translation;
if (seq[0].cross(point) != 1 &&
sgn(seq[0].cross(point)) != sgn(seq[0].cross(seq[n - 1])))
return false;
if (seq[n - 1].cross(point) != 0 &&
sgn(seq[n - 1].cross(point)) != sgn(seq[n - 1].cross(seq[0])))
return false;
if (seq[0].cross(point) == 0)
return seq[0].sqrLen() >= point.sqrLen();
int l = 0, r = n - 1;
while (r - l > 1) {
int mid = (l + r) / 2;
int pos = mid;
if (seq[pos].cross(point) >= 0)
l = mid;
else
r = mid;
}
int pos = l;
return pointInTriangle(seq[pos], seq[pos + 1], pt(0, 0), point);
}
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int n,m,q;
cin>>n>>m>>q;
vector<pt> a,b;
REP(i,n){
int x,y;
cin>>x>>y;
a.pb({x,y});
}
REP(i,m){
int x,y;
cin>>x>>y;
b.pb({-x,-y});
}
convex_hull(a),convex_hull(b);
auto c=minkowski(a,b);
convex_hull(c);
prepare(c);
while(q--){
int dx,dy;
cin>>dx>>dy;
cout<<pointInConvexPolygon({dx,dy})<<'\n';
}
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3340kb
input:
5 5 500 6407435 3293303 7667584 -28726709 12981947 3232993 -4728920 -20310419 11417244 -21375059 -9897535 1003568 11250465 -455741 -212338 27421583 -8617310 23838234 1170809 22010017 9475604 -55467994 -4050339 3741774 -837777 3712301 21965125 2292518 15461481 -52915993 6607803 -55284619 4978498 3464...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st lines differ - expected: '1', found: '0'
Test #2:
score: 0
Wrong Answer
time: 2ms
memory: 3412kb
input:
5 5 500 -27523822 3903432 -8164905 12245974 -12788492 -18439238 -9257256 12571383 -7088899 -13518632 8395941 908038 3503624 10427724 -14313118 13946163 -8810192 15122696 -23606580 1742581 -2846782 -33320015 10422149 -23265478 -28254784 -10728385 -25177201 8093012 -7071570 -16767903 -24720747 8309611...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 4th lines differ - expected: '1', found: '0'
Test #3:
score: 0
Wrong Answer
time: 2ms
memory: 3420kb
input:
50 50 500 4254966 4514473 -10243311 29338943 -11714256 28967870 -3638225 -329846 -11636788 -126679 -5182905 -625577 6032976 21796923 -13140961 28452003 1041973 27162958 -2756343 -84802 -7820141 29623403 -1439665 28473013 -2457947 28853419 -7990305 29616231 -7601697 29629812 -14884269 1278440 -998615...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st lines differ - expected: '1', found: '0'
Test #4:
score: 0
Wrong Answer
time: 2ms
memory: 3448kb
input:
50 50 500 9401701 -3609043 2012208 -1102882 -1811540 -26010495 -5041437 -3110073 10286335 -4329717 12578870 -20602424 10667571 -4684127 12022858 -6227670 6703376 -2076756 -3916528 -2467881 -8883942 -6948248 4710266 -26206538 8123463 -24867007 5052685 -26121576 -4028108 -2524942 -1941055 -1669813 319...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st lines differ - expected: '1', found: '0'
Test #5:
score: 0
Wrong Answer
time: 8ms
memory: 4252kb
input:
10000 10000 500 1666056 -27430003 -4367330 9570472 18716225 -12240967 -1787485 -27373792 -15436704 1726451 5020083 -26867542 -2574044 -27271537 -11443050 6074066 -4820607 -26789265 15100955 2873536 -9623440 7349040 976214 10130141 -9144842 7634171 6079703 9216512 15077673 -20242861 16905511 69303 13...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 5th lines differ - expected: '1', found: '0'
Test #6:
score: 0
Wrong Answer
time: 11ms
memory: 4248kb
input:
10000 10000 500 9282217 -4781364 1501964 25031109 -3834648 -5391055 8360673 -5218666 -7317209 -3446949 -10874263 199999 -3638519 23977553 -10806642 104184 9180387 23342430 8585209 23627902 -742433 24790641 2593801 -6522640 -13108369 4871264 -3278720 24111737 -1204794 24700179 2670075 25028975 145219...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 6th lines differ - expected: '1', found: '0'
Test #7:
score: 0
Wrong Answer
time: 12ms
memory: 4200kb
input:
10000 10000 500 18739956 22581499 226899 20847190 4459986 -8474225 19625260 22085584 17107612 -8505721 1592846 21819795 4911498 -8647734 754040 -6425195 11298530 -9694797 8002434 -9467273 15632721 -9011669 19047199 -7595729 26034505 15249508 1304680 21631076 16199900 -8834823 20427260 -6752268 -5838...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 3rd lines differ - expected: '1', found: '0'
Test #8:
score: 0
Wrong Answer
time: 92ms
memory: 10980kb
input:
100000 100000 100000 24235601 -13951926 -10355885 -24094242 -5635989 -27027698 12252374 12885344 6137155 -28841530 15967851 10799403 9725989 13814468 -7061607 12038424 -9834599 -24505790 11646839 -27414386 -2187954 -28266157 -18126630 -3597220 3069276 14729493 -199316 14425458 11896146 -27311875 -12...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 3rd lines differ - expected: '1', found: '0'
Test #9:
score: 0
Wrong Answer
time: 111ms
memory: 9676kb
input:
100000 100000 100000 8354421 -26671439 8956353 6194768 18000019 5113843 -731040 989961 20842988 3589967 1941343 -23926046 17724523 5225919 26327648 -18097349 26513711 -2848520 19914037 -24750782 19992615 -24705163 -3889910 -4001319 26006870 -1907798 11797680 6399489 3081377 -24663720 14262223 -26766...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 3rd lines differ - expected: '1', found: '0'
Test #10:
score: 0
Wrong Answer
time: 119ms
memory: 9656kb
input:
100000 100000 100000 -17714771 -18844934 13960381 -21362034 -13107507 -24716099 -5216508 -28653304 -6830004 7079906 -7371497 6895381 15737377 -2830941 -16200790 -21359312 -17628244 -19016144 8224158 -26586063 -732489 7976996 13458776 -22030283 -5650557 -28549478 16498589 -4770663 4862335 -28120485 8...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st lines differ - expected: '1', found: '0'