QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#711001#5426. Drain the Water Tankucup-team2179WA 1ms3836kbC++233.9kb2024-11-04 23:42:112024-11-04 23:42:11

Judging History

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

  • [2024-11-04 23:42:11]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3836kb
  • [2024-11-04 23:42:11]
  • 提交

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]);
		while(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^r.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个字符)的部分作为字符串的初值





詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3836kb

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: 3836kb

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: 3556kb

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: -100
Wrong Answer
time: 1ms
memory: 3836kb

input:

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

output:

1

result:

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