QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#315147#7730. Convex CheckeryokeffWA 7ms35060kbC++205.2kb2024-01-27 00:25:082024-01-27 00:25:09

Judging History

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

  • [2024-07-04 19:27:17]
  • hack成功,自动添加数据
  • (/hack/727)
  • [2024-07-04 19:17:30]
  • hack成功,自动添加数据
  • (/hack/726)
  • [2024-01-27 00:25:09]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:35060kb
  • [2024-01-27 00:25:08]
  • 提交

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: 0
Wrong Answer
time: 7ms
memory: 35060kb

input:

3
0 0
1 0
0 1

output:

0 2
YES

result:

wrong output format YES or NO expected, but 0 found