QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#315150 | #7730. Convex Checker | yokeff | WA | 0ms | 35116kb | C++20 | 5.3kb | 2024-01-27 00:25:39 | 2024-01-27 00:25:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
typedef pair<int, int> PII;
#define fr(i, a, n) for(int i = a; i <= n; i ++)
#define rf(i, a, n) for(int i = n; i >= a; i --)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int T, t, n, m, idx, flag, a1, b1, a2, b2, k, x, y, mx, mn;
int mid, mi, c, z, d, e;
int ans, sum, cnt;
int q[N], tr[N * 2], p[N], l[N], r[N], head[N];
string s1, s2, s3, s4, s5;
int ss[30];
vector<string> num[150];
double a, b;
const double eps = 1e-6;
struct point
{
double x, y;
point(double x = 0, double y = 0):x(x),y(y){}
};
typedef point Vector;
Vector operator + (Vector a, Vector b)
{
return Vector(a.x + b.x, a.y + b.y);
}
Vector operator - (Vector a, Vector b)
{
return Vector(a.x - b.x, a.y - b.y);
}
Vector operator * (Vector a, double p)
{
return Vector(a.x * p, a.y * p);
}
Vector operator / (Vector a, double p)
{
return Vector(a.x / p, a.y / p);
}
int sgn(double x)
{
if(fabs(x) < eps) return 0;
if(x < 0) return -1;
else return 1;
}
int dcmp(double x, double y)//点与点比较
{
if(fabs(x - y) < eps) return 0;
if(x > y) return 1;
else return -1;
}
double dot(Vector a, Vector b)//点乘
{
return a.x * b.x + a.y * b.y;
}
double cross(Vector a, Vector b)//叉乘
{
return a.x * b.y - a.y * b.x;
}
double length(Vector a)//取模
{
return sqrt(dot(a, a));
}
double angle(Vector a, Vector b)//夹角,返回弧度制
{
return acos(dot(a, b) / length(a) / length(b));
}
double area2(point a, point b, point c)//ab与ac构成的有向四边形面积
{
return cross(b - a, c - a);
}
Vector rotate(Vector a, double rad)//rad为弧度制,且为逆时针旋转的角
{
return Vector(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad));
}
Vector normal(Vector a)//向量a左转90°的单位法向量
{
double L = length(a);
return Vector(-a.y / L, a.x / L);
}
bool tolefttest(point a, point b, point c)//判断bc在ab的逆时针方向(左侧),是返回1,
{
return cross(b - a, c - b) > 0;
}
point lst[N], qq[N];
int stk[N], top;
bool cmp(point a, point b)
{
int s = sgn(cross(a - lst[0], b - lst[0]));
if(s > 0) return true;
if(s == 0 && length(a - lst[0]) < length(b - lst[0])) return true;
else return false;
}
bool cmp1(point a, point b)
{
int s = sgn(cross(a - lst[0], b - lst[0]));
if(s > 0) return true;
if(s == 0 && length(a - lst[0]) < length(b - lst[0])) return true;
else return false;
}
void Graham()
{
k = 0;
point p0;
a = lst[0].x;
b = lst[0].y;
for(int i = 1; i < n; i ++)
{
if(b > lst[i].y || (b == lst[i].y && a > lst[i].x))
{
a = lst[i].x;
b = lst[i].y;
k = i;
}
}
if(n == 1)
{
top = 1;
stk[0] = 0;
return ;
}
if(n == 2)
{
top = 2, stk[0] = 0, stk[1] = 1;
return ;
}
stk[0] = k, stk[1] = k + 1, top = 2;
// cout << k << ' ' << top << endl;
for(int i = k + 2; i < n + k; i ++)
{
// cout << i << ' ' << lst[stk[top - 1]].x << ' ' << lst[stk[top - 1]].y << ' ' << lst[stk[top - 2]].x << ' ' << lst[stk[top - 2]].y << ' ' << lst[i].x << " " << lst[i].y << endl;
// cout << i << ' ' << cross(lst[stk[top - 1]] - lst[stk[top - 2]], lst[i] - lst[stk[top - 2]]) << endl;
while(top > 1 && cross(lst[stk[top - 1]] - lst[stk[top - 2]], lst[i] - lst[stk[top - 2]]) <= 0)
{
top --;
}
stk[top] = i;
top ++;
}
if(top == n)
{
fr(i, 0, n - 1) qq[i] = lst[i];
sort(qq, qq + n, cmp);
flag = 1;
for(int i = k; i < k + n; i ++)
{
if(qq[i - k].x != lst[i].x && lst[i].y != qq[i - k].y) flag = 0;
}
if(flag == 1)
{
top = n;
return ;
}
}
fr(i, 0, n - 1) qq[i] = lst[n - i - 1];
fr(i, 0, n - 1) lst[i] = qq[i];
k = 0;
a = lst[0].x;
b = lst[0].y;
for(int i = 1; i < n; i ++)
{
if(b > lst[i].y || (b == lst[i].y && a > lst[i].x))
{
a = lst[i].x;
b = lst[i].y;
k = i;
}
}
if(n == 1)
{
top = 1;
stk[0] = 0;
return ;
}
if(n == 2)
{
top = 2, stk[0] = 0, stk[1] = 1;
return ;
}
stk[0] = k, stk[1] = k + 1, top = 2;
cout << k << ' ' << top << endl;
for(int i = k + 2; i < n + k; i ++)
{
// cout << i << ' ' << lst[stk[top - 1]].x << ' ' << lst[stk[top - 1]].y << ' ' << lst[stk[top - 2]].x << ' ' << lst[stk[top - 2]].y << ' ' << lst[i].x << " " << lst[i].y << endl;
// cout << i << ' ' << cross(lst[stk[top - 1]] - lst[stk[top - 2]], lst[i] - lst[stk[top - 2]]) << endl;
while(top > 1 && cross(lst[stk[top - 1]] - lst[stk[top - 2]], lst[i] - lst[stk[top - 2]]) <= 0)
{
top --;
}
stk[top] = i;
top ++;
}
if(top == n)
{
fr(i, 0, n - 1) qq[i] = lst[i];
sort(qq, qq + n, cmp);
flag = 1;
for(int i = k; i < k + n; i ++)
{
if(qq[i - k].x != lst[i].x && lst[i].y != qq[i - k].y) flag = 0;
}
if(flag == 1)
{
top = n;
return ;
}
}
}
void solve()
{
cin >> n;
set<PII> st;
fr(i, 0, n - 1)
{
cin >> a >> b;
st.insert({a, b});
lst[i] = {a, b};
lst[i + n] = {a, b};
}
Graham();
// cout << top << endl;
if(st.size() >= 3 && top == n)
{
cout << "YES" << endl;
}else cout << "NO" << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
// cin >> T;
// while(T -- )
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 35116kb
input:
3 0 0 1 0 0 1
output:
YES
result:
ok answer is YES
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 35004kb
input:
4 0 0 0 1 1 1 1 0
output:
3 2 NO
result:
wrong output format YES or NO expected, but 3 found