QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#711007 | #5426. Drain the Water Tank | ucup-team2179 | TL | 1ms | 3840kb | C++23 | 4.0kb | 2024-11-04 23:45:08 | 2024-11-04 23:45:08 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define ll __int128
#define db double
#define pb push_back
bool debug=1;
#define dbg(x) if(debug)cerr << BRIGHT_CYAN << #x << COLOR_RESET << " = " << (x) << NORMAL_FAINT << " (L" << __LINE__ << ") " << __FILE__ << COLOR_RESET << endl
using namespace std;void ass(string err){cout<<err<<"\n";exit(0);}void ass(int err){cout<<err<<"\n";exit(0);}
typedef pair<int,int> pii;
const string COLOR_RESET = "\033[0m", BRIGHT_CYAN = "\033[1;36m", NORMAL_FAINT = "\033[0;2m";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int eps=0;
const long double PI=3.1415926535897932384l;
template<typename T> struct Point
{
T x,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)};}
};
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<int>;
using L=Line<int>;
void solve()
{
int n;
cin>>n;
vector<P>a;
for(int i=0;i<n;i++){
int x,y;
cin>>x>>y;
a.pb({x,y});
}
int ans=0;
int r=0;
for(int i=0;i<n;i++){
L l=L(a[(i-1+n)%n],a[i]-a[(i-1+n)%n]);
L l2=L(a[i],a[(i+1)%n]-a[i]);
while(i<n&&a[i].y==a[(i+1)%n].y)i=(i+1)%n;
L r=L(a[i],a[(i+1)%n]-a[i]);
if(l.v.y<0&&r.v.y>=0&&(l.v^l2.v)>=0)ans++;
}
cout<<ans;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int t=1;
// cin>>t;
while(t--)
{
solve();
if(t)cout<<'\n';
}
return 0;
}
//__builtin_popcountll( ) 计算二进制1个数
//cout<<fixed<<setprecision(2);输出小数,四舍六入五取偶
//__builtin_ctzll( )返回末尾0的个数
//__builtin_clzll( ) 返回前导0的个数
//__builtin_parityll( )返回1的个数的奇偶性,偶数返回0
//__builtin_ffsll( )返回最后一个1在第几位
//__builtin_sqrt( )快速开平方
//stoll()字符串转为长整形
//点(x,y)的极角atan2(y,x)
//点(x,y)逆时针旋转A度,(x*cosA-y*sinA , x*sinA+y*cosA )
//C(n,k)+C(n,k-1)=(n+1,k)
//string s(str,stridx,strlen) //将字符串str内“始于stridx且长度顶多strlen”
//(从stridx开始往后strlen个字符)的部分作为字符串的初值
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3620kb
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: 1ms
memory: 3616kb
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: 1ms
memory: 3564kb
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: 3808kb
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: 0
Accepted
time: 0ms
memory: 3692kb
input:
8 0 0 1 0 3 -1 3 0 1 1 4 1 5 0 3 4
output:
2
result:
ok 1 number(s): "2"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
5 0 0 170 0 140 30 60 30 0 70
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
5 0 0 170 0 140 30 60 30 0 100
output:
1
result:
ok 1 number(s): "1"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
5 0 0 1 2 1 5 0 2 0 1
output:
1
result:
ok 1 number(s): "1"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
3 0 0 100 0 0 100
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: -100
Time Limit Exceeded
input:
3 200 0 100 100 0 0