K - Number Deletion Game
statements
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1010;
int a[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int mx=*max_element(a+1,a+n+1);
int cnt=count(a+1,a+n+1,mx);
if(cnt&1) cout<<"Alice\n";
else cout<<"Bob\n";
return 0;
}
I - Integer Reaction
statements
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N],c[N];
int n;
bool check(int x){
multiset<int> s1,s2;
for(int i=1;i<=n;i++){
if(c[i]==0){
if(s2.size()){
auto it=s2.lower_bound(x-a[i]);
if(it==s2.end()) return 0;
else s2.erase(it);
}
else s1.insert(a[i]);
}
else{
if(s1.size()){
auto it=s1.lower_bound(x-a[i]);
if(it==s1.end()) return 0;
else s1.erase(it);
}
else s2.insert(a[i]);
}
}
return 1;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
while(t--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>c[i];
int l=0,r=1e9;
int ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
cout<<ans<<'\n';
}
return 0;
}
B - Area of the Devil
statements
#include <bits/stdc++.h>
using namespace std;
using std::numeric_limits;
using std::abs, std::max, std::min, std::swap;
using std::pair, std::make_pair;
using std::tuple, std::make_tuple;
using std::vector, std::deque;
using std::set, std::multiset;
using std::cin,std::cout;
using T=long double; //全局数据类型
constexpr T eps=1e-9;
constexpr T INF=numeric_limits<T>::max();
constexpr T PI=3.1415926535897932384l;
// 点与向量
struct Point
{
T x,y;
bool operator==(const Point &a) const {return (abs(x-a.x)<=eps && abs(y-a.y)<=eps);}
bool operator<(const Point &a) const {if (abs(x-a.x)<=eps) return y<a.y-eps; return x<a.x-eps;}
bool operator>(const Point &a) const {return !(*this<a || *this==a);}
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;} // 点积
T operator^(const Point &a) const {return x*a.y-y*a.x;} // 叉积，注意优先级
int toleft(const Point &a) const {const auto t=(*this)^a; return (t>eps)-(t<-eps);} // to-left 测试
T len2() const {return (*this)*(*this);} // 向量长度的平方
T dis2(const Point &a) const {return (a-(*this)).len2();} // 两点距离的平方
int quad() const // 象限判断 0:原点 1:x轴正 2:第一象限 3:y轴正 4:第二象限 5:x轴负 6:第三象限 7:y轴负 8:第四象限
{
if (abs(x)<=eps && abs(y)<=eps) return 0;
if (abs(y)<=eps) return x>eps ? 1 : 5;
if (abs(x)<=eps) return y>eps ? 3 : 7;
return y>eps ? (x>eps ? 2 : 4) : (x>eps ? 8 : 6);
}
// 必须用浮点数
T len() const {return sqrtl(len2());} // 向量长度
T dis(const Point &a) const {return sqrtl(dis2(a));} // 两点距离
T ang(const Point &a) const {return acosl(max(-1.0l,min(1.0l,((*this)*a)/(len()*a.len()))));} // 向量夹角
Point rot(const T rad) const {return {x*cos(rad)-y*sin(rad),x*sin(rad)+y*cos(rad)};} // 逆时针旋转（给定角度）
Point rot(const T cosr,const T sinr) const {return {x*cosr-y*sinr,x*sinr+y*cosr};} // 逆时针旋转（给定角度的正弦与余弦）
};
// 极角排序
struct Argcmp
{
bool operator()(const Point &a,const Point &b) const
{
const int qa=a.quad(),qb=b.quad();
if (qa!=qb) return qa<qb;
const auto t=a^b;
// if (abs(t)<=eps) return a*a<b*b-eps; // 不同长度的向量需要分开
return t>eps;
}
};
// 直线
struct Line
{
Point p,v; // p 为直线上一点，v 为方向向量
bool operator==(const Line &a) const {return v.toleft(a.v)==0 && v.toleft(p-a.p)==0;}
int toleft(const Point &a) const {return v.toleft(a-p);} // to-left 测试
bool operator<(const Line &a) const // 半平面交算法定义的排序
{
if (abs(v^a.v)<=eps && v*a.v>=-eps) return toleft(a.p)==-1;
return Argcmp()(v,a.v);
}
// 必须用浮点数
Point inter(const Line &a) const {return p+v*((a.v^(p-a.p))/(v^a.v));} // 直线交点
T dis(const Point &a) const {return abs(v^(a-p))/v.len();} // 点到直线距离
Point proj(const Point &a) const {return p+v*((v*(a-p))/(v*v));} // 点在直线上的投影
friend bool line_intersection(const Line &l1, const Line &l2, Point &res) {
T det = l1.v ^ l2.v; // 两方向向量的叉积
if (fabsl(det) < 1e-9) return false; // 平行或重合（无交点或无穷多交点）
T t = ((l2.p - l1.p) ^ l2.v) / det;
res = l1.p + l1.v * t;
return true;
}
};
//线段
struct Segment
{
Point a,b;
bool operator<(const Segment &s) const {return make_pair(a,b)<make_pair(s.a,s.b);}
// 判定性函数建议在整数域使用
// 判断点是否在线段上
// -1 点在线段端点 | 0 点不在线段上 | 1 点严格在线段上
int is_on(const Point &p) const
{
if (p==a || p==b) return -1;
return (p-a).toleft(p-b)==0 && (p-a)*(p-b)<-eps;
}
// 判断线段直线是否相交
// -1 直线经过线段端点 | 0 线段和直线不相交 | 1 线段和直线严格相交
int is_inter(const Line &l) const
{
if (l.toleft(a)==0 || l.toleft(b)==0) return -1;
return l.toleft(a)!=l.toleft(b);
}
// 判断两线段是否相交
// -1 在某一线段端点处相交 | 0 两线段不相交 | 1 两线段严格相交
int is_inter(const Segment &s) const
{
if (is_on(s.a) || is_on(s.b) || s.is_on(a) || s.is_on(b)) return -1;
const Line l{a,b-a},ls{s.a,s.b-s.a};
return l.toleft(s.a)*l.toleft(s.b)==-1 && ls.toleft(a)*ls.toleft(b)==-1;
}
// 点到线段距离（必须用浮点数）
T dis(const Point &p) const
{
if ((p-a)*(b-a)<-eps || (p-b)*(a-b)<-eps) return min(p.dis(a),p.dis(b));
const Line l{a,b-a};
return l.dis(p);
}
// 两线段间距离（必须用浮点数）
T dis(const Segment &s) const
{
if (is_inter(s)) return 0;
return min({dis(s.a),dis(s.b),s.dis(a),s.dis(b)});
}
};
int main(){
int t;
cin>>t;
while(t--){
int r;
cin>>r;
Point p[3][6];
int tmp[3][6];
for(int i=1;i<=2;i++){
for(int j=0;j<5;j++){
int x;
cin>>x;
tmp[i][j]=x;
p[i][j]=Point{r*cos(PI*x/180),r*sin(PI*x/180)};
}
}
T ans=PI*r*r;
for(int i=0;i<5;i++){
Line l{p[2][i],p[1][(i+1)%5]-p[2][i]};
Line l1{p[2][i],p[1][(i+2)%5]-p[2][i]};
Line l2{p[1][(i+1)%5],p[2][(i+4)%5]-p[1][(i+1)%5]};
Point jd;
line_intersection(l1,l2,jd);
// T angel=p[2][i].ang(p[1][get_index(i+1)]);
T angel=1.0*(tmp[1][(i+1)%5]-tmp[2][i])/360*2*PI;
if(angel<0) angel+=2*PI;
// cout<<angel<<'\n';
T area_sector=r*r*angel/2;
//cout<<angel<<'\n';
T area_triangle=(p[2][i]^p[1][(i+1)%5])/2;
T area_triangle2=((p[2][i]-jd)^(p[1][(i+1)%5]-jd))/2;
ans-=area_sector-area_triangle+area_triangle2;
}
cout<<fixed<<setprecision(10)<<ans<<'\n';
}
}
B - Area of the Devil
statements
