QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#790089 | #5417. Chat Program | ucup-team3646 | WA | 0ms | 3620kb | C++20 | 2.3kb | 2024-11-28 00:51:34 | 2024-11-28 00:51:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define rep2(i, l, r) for (ll i = l; i < r; i++)
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
#define all(A) A.begin(), A.end()
#define elif else if
using pii = pair<ll, ll>;
bool chmin(auto &a, const auto &b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto &a, const auto &b) { return a < b ? a = b, 1 : 0; }
struct IOSetup {
IOSetup() {
cin.tie(0);
ios::sync_with_stdio(0);
}
} iosetup;
template <class T>
void print(vector<T> a) {
for (auto x : a) cerr << x << ' ';
cout << endl;
}
void print(auto x) { cout << x << endl; }
template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail) {
cout << head << ' ';
print(forward<Tail>(tail)...);
}
using Real = double;
using Point = complex<Real>;
using Poly = vector<Point>;
Real eps = 1e-9;
int Round(Real x) { return static_cast<int>(round(x)); }
// 同じか判定
bool equal(Point a, Point b) { return abs(a - b) < eps; }
// 内積(dot product): a・b=|a||b|cosΘ
Real dot(Point a, Point b) { return a.real() * b.real() + a.imag() * b.imag(); }
// 外積(cross product): a×b=|a||b|sinΘ
Real cross(Point a, Point b) { return a.real() * b.imag() - a.imag() * b.real(); }
Point unitVector(Point p) { return p / abs(p); }
// 多角形 g に点 p が含まれるか? 含む:2, 辺上:1, 含まない:0
int isContain(Poly g, Point p) {
int IN = 0;
int n = g.size();
rep(i, n) {
Point a = g[i] - p;
Point b = g[(i + 1) % n] - p;
if (a.imag() > b.imag()) swap(a, b);
if (imag(a) < eps && eps < imag(b) && cross(a, b) < -eps) IN ^= 1;
if (equal(cross(a, b), 0) && dot(a, b) < eps) return 1;
}
return 2 * IN;
}
int main(){
int n;
cin>>n;
vi x(n),y(n);
Poly g;
rep(i,n){
cin>>x[i]>>y[i];
y[i]*=100;
g.push_back(Point((Real)x[i],(Real)y[i]));
}
int ans=0;
rep(i,n){
if(y[(i-1+n)%n]<=y[i])continue;
int now=(i+1)%n;
while(y[i]==y[now]){
now++;
now%=n;
}
if(y[now]>y[i]){
Point p1=(g[(i-1+n)%n]-g[i]);
Point p2=(g[(i+1)%n]-g[i]);
Point q=g[i]+(p1+p2)*1e-4;
if(isContain(g,q)>=1)ans++;
}
}
cout<<ans<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3620kb
input:
6 4 3 1 2 1 1 4 5 1 4
output:
1
result:
wrong answer 1st numbers differ - expected: '4', found: '1'