QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#344894 | #3814. Saint John Festival | KhNURE_KIVI# | WA | 1ms | 3764kb | C++14 | 3.9kb | 2024-03-05 17:52:49 | 2024-03-05 17:52:50 |
Judging History
answer
//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#include <bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
template<typename T>
bool umin(T &a, T b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<typename T>
bool umax(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
#ifdef KIVI
#define DEBUG for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define DEBUG while (false)
#define LOG(...)
#endif
const int max_n = -1, inf = 2000111222;
struct Point
{
int x,y;
};
ostream& operator<<(ostream& os,const Point& a)
{
return os<<"{"<<a.x<<","<<a.y<<"}";
}
const bool operator<(const Point& lhs,const Point& rhs)
{
return mp(lhs.x,lhs.y)<mp(rhs.x,rhs.y);
}
Point operator-(const Point& lhs,const Point& rhs)
{
return Point{lhs.x-rhs.x,lhs.y-rhs.y};
}
bool cw(const Point& a,const Point& b)
{
return 1ll * a.x * b.y - 1ll * a.y * b.x < 0;
}
bool ccw(const Point& a,const Point& b)
{
return 0 < 1ll * a.x * b.y - 1ll * a.y * b.x;
}
bool cw(const Point& a,const Point& b,const Point& c)
{
return cw(b-a, c-b);
}
bool ccw(const Point& a,const Point& b,const Point& c)
{
return ccw(b-a, c-b);
}
pair<vector<Point>,vector<Point>> convex_hull(vector<Point> v)
{
sort(all(v));
if (len(v)<=2){
return mp(v,v);
}
vector<Point> up,down;
for (auto p:v){
if (!ccw(v[0],p,v.back())){
while (len(up)>=2 && !cw(up[len(up)-2],up.back(),p)){
up.pop_back();
}
up.pb(p);
}
}
for (auto p:v){
if (!cw(v[0],p,v.back())){
while (len(down)>=2 && !ccw(down[len(down)-2],down.back(),p)){
down.pop_back();
}
down.pb(p);
}
}
return mp(up,down);
}
int main() {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
vector<Point> v;
for (int i=0;i<n;i++){
int x,y;
cin>>x>>y;
v.pb(Point{x,y});
}
auto H=convex_hull(v);
auto up=H.fir;
auto down=H.sec;
DEBUG{
cerr<<"up :: ";
for (auto i:up){
cerr<<i<<" ";
}
cerr<<"\n";
cerr<<"down :: ";
for (auto i:down){
cerr<<i<<" ";
}
cerr<<"\n";
};
int ans=0;
int q;
cin>>q;
LOG(q);
while (q--){
int x,y;
cin>>x>>y;
LOG(x,y);
bool ok1=0;
bool ok2=0;
if (x>=up[0].x && x<=up.back().x){
int id=upper_bound(all(up),Point{x,+inf})-up.begin()-1;
id=min(id,len(up)-2);
const Point& a=up[id];
const Point& b=up[id+1];
LOG("for ok1",a,b);
ok1=!ccw(a,b,Point{x,y});
}
if (x>=down[0].x && x<=down.back().x){
int id=upper_bound(all(down),Point{x,+inf})-down.begin()-1;
id=min(id,len(down)-2);
const Point& a=down[id];
const Point& b=down[id+1];
LOG("for ok2",a,b);
ok2=!cw(a,b,Point{x,y});
}
if (ok1 && ok2){
LOG("to answer",x,y);
}
ans+=(ok1 && ok2);
}
cout<<ans<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3764kb
input:
4 1 1 4 1 4 4 1 4 32 0 0 1 0 2 0 3 0 4 0 5 0 0 1 2 1 3 1 5 1 0 2 1 2 2 2 3 2 4 2 5 2 0 3 1 3 2 3 3 3 4 3 5 3 0 4 2 4 3 4 5 4 0 5 1 5 2 5 3 5 4 5 5 5
output:
13
result:
wrong answer 1st lines differ - expected: '12', found: '13'