QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#671729#5426. Drain the Water TankpuremgWA 0ms3544kbC++145.4kb2024-10-24 14:12:562024-10-24 14:13:15

Judging History

你现在查看的是最新测评结果

  • [2024-10-24 14:13:15]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3544kb
  • [2024-10-24 14:12:56]
  • 提交

answer

//Author: Puremg
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC optimize(3,"Ofast")
#include <bits/stdc++.h>
#define deg(a) cout<<#a<<'='<<a<<"\n"
#define int long long
#define all(a) a.begin(), a.end()
// #define db double
#define ldb long double
#define db ldb
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e7+10;
const db eps = 1e-12;
const db pi = acos(-1);
mt19937_64 rng(random_device{}());
int sgn(ldb x) {
  if (fabs(x) < eps) return 0;
  else if (x > 0) return 1;
  else return -1;
}
template<typename T> struct Point
{
  T x,y;
  Point(){}
  Point(T x, T y):x(x),y(y){}
  bool operator==(const Point &a) const {return (abs(x-a.x)<=eps && abs(y-a.y)<=eps);}
  Point operator+(const Point &a) const {return {x+a.x,y+a.y};}
  Point operator-(const Point &a) const {return {x-a.x,y-a.y};}
  Point operator-() const {return {-x,-y};}
  Point operator*(const T k) const {return {k*x,k*y};}
  Point operator/(const T k) const {return {x/k,y/k};}
  T operator*(const Point &a) const {return x*a.x+y*a.y;} //Dot
  T operator^(const Point &a) const {return x*a.y-y*a.x;} //Cross
  bool operator<(const Point &a) const {if (abs(x-a.x)<=eps) return y<a.y-eps; return x<a.x-eps;}
  bool is_par(const Point &a) const {return abs((*this)^a)<=eps;}
  bool is_ver(const Point &a) const {return abs((*this)*a)<=eps;}
  int toleft(const Point &a) const {auto t=(*this)^a; return (t>eps)-(t<-eps);}
  T len2() const {return (*this)*(*this);}
  T dis2(const Point &a) const {return (a-(*this)).len2();}
  double len() const {return sqrt(len2());}
  double dis(const Point &a) const {return (a-(*this)).len();}
  double ang(const Point &a) const {return acos(((*this)*a)/(this->len()*a.len()));}
  Point rot(const double rad) const {return {x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad)};}
  int sign() const {
  if (y < 0 or (x > 0 and y == 0)) return 0;
    return 1;
  }
};
template<typename T> struct Line
{
    Point<T> p,v; //p+tv
    // Line(Point<T> p, Point<T> v) : p(p), v(v){}
    bool operator==(const Line &a) const {return (v.is_par(a.v) && v.is_par(p-a.p));}
    bool is_par(const Line &a) const {return (v.is_par(a.v) && !v.is_par(p-a.p));}
    bool is_ver(const Line &a) const {return v.is_ver(a.v);}
    bool is_on(const Point<T> &a) const {return v.is_par(a-p);} 
    int toleft(const Point<T> &a) const {return v.toleft(a-p);} // 直线和点的位置关系
    Point<T> inter(const Line &a) const {return p+v*((a.v^(p-a.p))/(v^a.v));} // 两条直线交点
    double dis(const Point<T> &a) const {return abs(v^(a-p))/v.len();}
    Point<T> proj(const Point<T> &a) const {return p+v*((v*(a-p))/(v*v));} // 点在这条直线的投影
};
using P = Point<ldb>;
using L = Line<ldb>;
bool is_point_on_segment(P a, P b, P p) {
  P ap = p - a, bp = p - b;
  if (sgn(ap^bp)==0 and (ap*bp)<=0) return 1;
  return 0; 
}
int is_point_in_polygon(P p, vector<P> &poly, int n) {
  int wn = 0;
  for (int i = 1; i <= n; i ++) {
    int left_test = (poly[i%n+1]-poly[i]).toleft(p-poly[i]);
    int d1 = sgn(poly[i].y - p.y), d2 = sgn(poly[i%n+1].y - p.y);
    if (left_test > 0 and d1 <= 0 and d2 > 0) wn ++;
    if (left_test < 0 and d1 > 0 and d2 <= 0) wn --;
  }
  return wn;
}
void solve() {
  int n;
  cin >> n;
  vector<P> a(n + 10);
  for (int i = 1; i <= n; i ++) {
    int x, y;
    cin >> x >> y;
    a[i].x = 1. * x;
    a[i].y = 1. * y;
  }
  int ans = 0;
  vector<int> ji(n + 10);
  for (int i = 1; i <= n; i ++) {
    int pre = i - 1;
    if (pre == 0) pre = n;
    int nxt = i + 1;
    if (nxt == n + 1) nxt = 1;
    if (sgn(a[pre].y - a[i].y) < 0 or sgn(a[nxt].y - a[i].y) < 0) continue;
    if (sgn(a[pre].y - a[i].y) == 0 or sgn(a[nxt].y - a[i].y) == 0) {
      while (sgn(a[nxt].y - a[i].y) == 0) {
        nxt ++;
        if (nxt == n + 1) {
          nxt = 1;
        }
      }
      nxt --;
      if (nxt == 0) nxt = n;
      while (sgn(a[pre].y - a[i].y) == 0) {
        pre --;
        if (pre == 0) {
          pre = n;
        }
      }
      if (a[pre].y < a[i].y or a[nxt].y < a[i].y) {

      } else {
        // deg(i);
        // deg(pre);
        // deg(nxt);
        P shang;
        shang.x = a[i].x;
        shang.y = a[i].y - 1e-7;
        int ok = (a[i] - a[pre]) ^ (a[nxt] - a[i]);
        // if (sgn(ok) > 0) {
        //   ans ++;
        // }
        if (not ji[pre] and not ji[nxt] and sgn(ok) > 0) {
          ans ++;
          ji[pre] = 1;
          ji[nxt] = 1;
        }
      }
    } else {
      P shang;
      shang.x = a[i].x;
      shang.y = a[i].y - 1e-7;
      int ok = is_point_in_polygon(shang, a, n);
      ok = (a[i] - a[pre]) ^ (a[nxt] - a[i]);
      if (sgn(ok) > 0) {
        ans ++;
      }
      // if (ok == 0) {
      //   ans ++;
      // }
    }
  }
  cout << ans;
}
signed main()
{
 // auto start_time = std::chrono::high_resolution_clock::now();
 // freopen("in.txt", "r", stdin);
 // freopen("out.txt", "w", stdout);
  cin.tie(nullptr)->sync_with_stdio(false);
  cout << fixed << setprecision(15);
  int T = 1;
  // cin >> T;
  while (T--) solve();
  // auto end_time = std::chrono::high_resolution_clock::now();
  // auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end_time - start_time);
  // std::cout << "程序运行时间:" << duration.count() << "毫秒" << std::endl;
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3532kb

input:

6
0 0
1 1
2 1
3 0
3 2
0 2

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3484kb

input:

8
4 4
0 4
0 2
1 2
2 2
2 0
3 0
4 0

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

7
1 0
3 4
0 3
1 2
2 3
1 1
0 2

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3460kb

input:

6
0 0
2 0
1 1
4 1
5 0
3 4

output:

2

result:

ok 1 number(s): "2"

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3480kb

input:

8
0 0
1 0
3 -1
3 0
1 1
4 1
5 0
3 4

output:

3

result:

wrong answer 1st numbers differ - expected: '2', found: '3'