QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#314476 | #7730. Convex Checker | lmf_up | WA | 1ms | 3660kb | C++20 | 5.2kb | 2024-01-25 18:51:42 | 2024-01-25 18:51:42 |
Judging History
answer
#include<bits/stdc++.h>
#define cp const point &
#define cl const line &
#define cc const circle
#define LD long double
const LD eps = 1e-8;
int sgn(LD x)
{
return x > eps ? 1 : (x < -eps ? -1 : 0);
}
LD sqr(LD x)
{ return x * x; }
struct point
{
LD x, y;
point operator+(cp a) const
{ return {x + a.x, y + a.y}; }
point operator-(cp a) const
{ return {x - a.x, y - a.y}; }
point operator*(LD t) const
{ return {x * t, y * t}; }
point operator/(LD t) const
{ return {x / t, y / t}; }
point rot(LD t) const
{ return {x * cos(t) - y * sin(t), x * sin(t) + y * cos(t)}; }
point rot90() const
{ return {-y, x}; }
double len2() const
{ return x * x + y * y; }
double len() const
{ return sqrt(x * x + y * y); }
point unit() const
{
double d = len();
return {x / d, y / d};
}
friend bool operator<(cp a,cp b)
{
if(a.x!=b.x)
return a.x<b.x;
else return a.y<b.y;
}
};
LD dot(cp a, cp b);
bool operator==(cp a, cp b)
{
return sgn(dot(a - b, a - b));
}
LD dis(cp a, cp b)
{
return sqrtl(sqr(a.x - b.x) +sqr(a.y - b.y));
}
LD dot(cp a, cp b)
{
return a.x * b.x + a.y * b.y;
}
LD det(cp a, cp b)
{
return a.x * b.y - b.x * a.y;
}
bool turn_left(cp a, cp b, cp c)
{
return sgn(det(b - a, c - a)) >=0;//大于等于是严格凸包,大于是非严格凸包可以有180°
}
struct line
{
point s, t;
line(point a,point b):s(a),t(b){}
};
bool same_dir(cl a, cl b)
{
return sgn(det(b.t - b.s, a.t - a.s)) == 0 && sgn(dot(b.t - b.s, a.t - a.s)) > 0;
}
bool point_on_segment(cp a, cl l)//前一句是点在直线上
{
return sgn(det(l.s - a, a - l.t)) == 0 && sgn(dot(l.s - a, a - l.t)) <= 0;
}
bool two_side(cp a,cp b,cl c)
{
return sgn(det(a-c.s,c.t-c.s))*sgn(det(b-c.s,c.t-c.s))<0;
}
bool intersect_judge(cl a,cl b){
if(point_on_segment(a.s,b)|| point_on_segment(a.t,b)|| point_on_segment(b.s,a)|| point_on_segment(b.t,a))return true;
return two_side(a.s,a.t,b)&& two_side(b.s,b.t,a);
}
point line_intersect(cl a,cl b){
double s1=det(a.t-a.s,b.s-a.s);
double s2=det(a.t-a.s,b.t-a.s);
return (b.s*s2-b.t*s1)/(s2-s1);
}
bool point_on_ray(cp a,cl b){
return sgn(det(a-b.s,b.t-b.s))==0&&sgn(dot(a-b.s,b.t-b.s))>=0;
}
bool ray_intersect_judge(line a,line b)
{
double s1,s2;
s1=det(a.t-a.s,b.s-a.s);
s2=det(a.t-a.s,b.t-a.s);
if(sgn(s1)==0&&sgn(s2)==0)
return sgn(dot(a.t-a.s,b.s-a.s))>=0||sgn(dot(b.t-b.s,a.s-b.s));
if(!sgn(s1-s2)||sgn(s1)==sgn(s2-s1))return 0;
std::swap(a,b);
s1=det(a.t-a.s,b.s-a.s);
s2=det(a.t-a.s,b.t-a.s);
return sgn(s1)!=sgn(s2-s1);
}
LD point_to_line(cp a,cl b){
return abs(det(b.t-b.s,a-b.s))/dis(b.s,b.t);
}
point project_to_line(cp a,cl b){
return b.s+(b.t-b.s)*(dot(a-b.s,b.t-b.s)/(b.t-b.s).len2());
}
LD point_to_segment(cp a,cl b){
if(sgn(dot(b.s-a,b.t-b.s))* sgn(dot(b.t-a,b.t-b.s))<=0)
return abs(det(b.t-b.s,a-b.s))/dis(b.s,b.t);
return std::min(dis(a,b.s),dis(a,b.t));
}
std::vector <point> convex_hull (std::vector <point> a) {
int n = (int) a.size (), cnt = 0;
if (n < 2) return a;
std::sort(a.begin(), a.end()); // less<pair>
std::vector <point> ret;
for (int i = 0; i < n; ++i) {
while (cnt > 1
&& turn_left (ret[cnt - 2], a[i], ret[cnt - 1]))
--cnt, ret.pop_back ();
++cnt, ret.push_back (a[i]); }
int fixed = cnt;
for (int i = n - 2; i >= 0; --i) {
while (cnt > fixed
&& turn_left (ret[cnt - 2], a[i], ret[cnt - 1]))
--cnt, ret.pop_back ();
++cnt, ret.push_back (a[i]); }
ret.pop_back (); return ret;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0),std::cout.tie(0);
std::cout<<std::fixed<<std::setprecision(2);
int n;
std::cin>>n;
std::vector<point>tu;
for(int i=1;i<=n;i++)
{
double x ,y;
std::cin>>x>>y;
tu.push_back({x,y});
}
auto res= convex_hull(tu);
if(res.size()!=n)
{
std::cout<<"No\n";
return 0;
}
for(int i=0;i<n;i++)
{
if(res[i]==tu[0])
{
int flag=1;
for(int j=0;j<n;j++)
{
if(res[(i+j)%n]==tu[j])
continue;
else
{
flag=0;
break;
// std::cout<<"No\n";
// return 0;
}
}
if(flag)
std::cout<<"Yes\n";
flag=1;
std::reverse(tu.begin(),tu.end());
for(int j=0;j<n;j++)
{
if(res[(i+j)%n]==tu[j])
continue;
else
{
flag=0;
break;
// std::cout<<"No\n";
// return 0;
}
}
if(flag)
std::cout<<"Yes\n";
else std::cout<<"No\n";
return 0;
}
}
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3660kb
input:
3 0 0 1 0 0 1
output:
Yes No
result:
wrong output format Extra information in the output file