QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#277322#7906. Almost ConvexSSH#Compile Error//C++204.4kb2023-12-06 17:46:162023-12-06 17:46:18

Judging History

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

  • [2023-12-06 17:46:18]
  • 评测
  • [2023-12-06 17:46:16]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve();

struct pt 
{
	int x, y;
	pt operator + (pt p) { return {x + p.x, y + p.y}; }
	pt operator - (pt p) { return {x - p.x, y - p.y}; }
	bool operator ==(pt p) { return (x == p.x && y == p.y); }
	int cross(pt p) { return x * p.y - y * p.x; }
	int cross(pt a, pt b) { return (a - *this).cross(b - *this); }
	int dot(pt p) { return x * p.x + y * p.y; }
};
bool cmp_x(pt a, pt b)
{
	if (a.x != b.x)
		return a.x < b.x;
	return a.y < b.y;
}
vector<pt> convex_hull(vector<pt> pts)
{
	if (pts.size() <= 1)
		return pts;
	sort(pts.begin(), pts.end(), cmp_x);
	vector<pt> h(pts.size() + 1);
	int s = 0, t = 0;
	for (int it = 2; it--; s = --t, reverse(pts.begin(), pts.end()))
	{
		for (auto const &p : pts)
		{
			while(t >= s + 2 && h[t - 2].cross(h[t - 1], p) <= 0) t--;
			h[t++] = p;
		}
	}
	return {h.begin(), h.begin() + t  - (t == 2 && h[0] == h[1])};
}//求点集的凸包
int sgn(int x)
{
	return (x > 0) - (x < 0);
}
int side_of(pt s, pt e, pt p) 
{
	return sgn(s.cross(e, p));
}
bool on_segment(pt s, pt e, pt p) 
{
	return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0;
}
bool is_hull(vector<pt> &l, pt p, bool strict = true)
{
	int a = 1, b = l.size() - 1, r = !strict;
	if (l.size() < 3)
		return r && on_segment(l[0], l.back(), p);
	if (side_of(l[0], l[a], l[b]) > 0) swap(a, b);
	if (side_of(l[0], l[a], p) >= r || side_of(l[0], l[b], p) <= -r)
		return false;
	while(abs(a - b) > 1)
	{
		int c = (a + b) / 2;
		(side_of(l[0], l[c], p) > 0 ? b : a) = c;
	}
	return sgn(l[a].cross(l[b], p)) < r;
}//判断点是否在凸包内(true在凸包内)

#define pb push_back

const int N = 500010;
const double eps = 1e-8;

inline bool equals(double a, double b)//判断相等
{
	return fabs(a - b) < eps;
}

struct Point//点 向量
{
	double x, y;
	Point() {}
	Point(double x, double y) :x(x), y(y) {}
	
	Point operator + (Point& b)
	{
		return Point(x + b.x, y + b.y);
	}
	
	Point operator - (Point& b)
	{
		return Point(x - b.x, y - b.y);
	}
	
	Point operator * (double k)
	{
		return Point(x * k, y * k);
	}
	
	Point operator / (double k)
	{
		return Point(x / k, y / k);
	}
	
	bool operator < (Point b)
	{
		return equals(x, b.x) ? y < b.y : x < b.x;
	}
	friend bool operator != (Point a, Point b){
		return a.x != b.x || a.y != b.y;
	}
};

typedef Point Vector;

inline double get_atan2(Point a, Point b)//求极角
{
	Vector v = b - a;
	return atan2(v.y, v.x);
}

struct Segment//线段 直线 射线
{
	Point p1, p2;//若表示射线则起点为p1
	double ang;
	Segment() {}
	Segment(Point a, Point b) :p1(a), p2(b), ang(get_atan2(p1, p2)) {}
	friend  operator < (Segment a, Segment b){
		if(a.p1 != b.p1){
			return a.p1 < b.p1;
		}
		else return a.p2 < b.p2;
	}
};
inline bool cmp_ang(Segment a, Segment b)//极角排序
{
	return a.ang < b.ang;
}
signed main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	int T = 1;
	//cin >> T;
	while(T--){
		solve();
	}
	return 0;
}
void solve(){
	int n;
	cin>>n;
	vector<pt>v(n);
	for(int i=0;i<n;i++) {
		cin>>v[i].x>>v[i].y;
	}
	vector<pt>res=convex_hull(v);//求凸包
//	for(auto [x,y]:res){
//		cout << x << " " << y << "\n";
//	}
	int ans = 1;
	for(int i=0;i<n;i++) {
		if(is_hull(res,v[i])) {//判断点是否在凸包内
			vector<Segment> a;
			for(auto [x,y]:res){
				a.push_back(Segment({v[i].x,v[i].y},{x,y}));
			}
			vector<Segment> b;
			for(int j = 0;j < n;j++){
				if(i != j){
					b.push_back(Segment({v[i].x,v[i].y}, {v[j].x,v[j].y}));
				}
			}
			map<Segment, int> mp;
			int idx = 0;
			sort(a.begin(), a.end(), cmp_ang);
			sort(b.begin(), b.end(), cmp_ang);
			for(auto s:b){
				mp[s] = idx++;
			}
//			cout << i << "\n";
//			cout << "a:\n";
//			for(auto s:a){
//				cout << s.p2.x << " " << s.p2.y << "\n";
//			}
//			cout << "b:\n";
//			for(auto s:b){
//				cout << s.p2.x << " " << s.p2.y << "\n";
//			}
			for(int j = 0;j < a.size();j++){
				int z = a.size();
				int nj = (j + 1) % z;
				if(abs(mp[a[j]] - mp[a[nj]]) == 1){
					//cout << i << "\n";
					ans++;
				}
				else if(mp[a[j]] == (int)b.size() - 1 && mp[a[nj]] == 0){
					//cout << i << "\n";
					ans++;
				}
				else if(mp[a[j]] == 0 && mp[a[nj]] == (int)b.size() - 1){
					//cout << i << "\n";
					ans++;
				}
			}
		}
	}
	cout << ans << "\n";
}

Details

answer.code:126:17: error: ISO C++ forbids declaration of ‘operator<’ with no type [-fpermissive]
  126 |         friend  operator < (Segment a, Segment b){
      |                 ^~~~~~~~
answer.code: In function ‘void solve()’:
answer.code:163:59: warning: narrowing conversion of ‘v.std::vector<pt>::operator[](((std::vector<pt>::size_type)i)).pt::x’ from ‘long long int’ to ‘double’ [-Wnarrowing]
  163 |                                 a.push_back(Segment({v[i].x,v[i].y},{x,y}));
answer.code:163:66: warning: narrowing conversion of ‘v.std::vector<pt>::operator[](((std::vector<pt>::size_type)i)).pt::y’ from ‘long long int’ to ‘double’ [-Wnarrowing]
  163 |                                 a.push_back(Segment({v[i].x,v[i].y},{x,y}));
answer.code:163:70: warning: narrowing conversion of ‘x’ from ‘long long int’ to ‘double’ [-Wnarrowing]
  163 |                                 a.push_back(Segment({v[i].x,v[i].y},{x,y}));
      |                                                                      ^
answer.code:163:72: warning: narrowing conversion of ‘y’ from ‘long long int’ to ‘double’ [-Wnarrowing]
  163 |                                 a.push_back(Segment({v[i].x,v[i].y},{x,y}));
      |                                                                        ^
answer.code:168:67: warning: narrowing conversion of ‘v.std::vector<pt>::operator[](((std::vector<pt>::size_type)i)).pt::x’ from ‘long long int’ to ‘double’ [-Wnarrowing]
  168 |                                         b.push_back(Segment({v[i].x,v[i].y}, {v[j].x,v[j].y}));
answer.code:168:74: warning: narrowing conversion of ‘v.std::vector<pt>::operator[](((std::vector<pt>::size_type)i)).pt::y’ from ‘long long int’ to ‘double’ [-Wnarrowing]
  168 |                                         b.push_back(Segment({v[i].x,v[i].y}, {v[j].x,v[j].y}));
answer.code:168:84: warning: narrowing conversion of ‘v.std::vector<pt>::operator[](((std::vector<pt>::size_type)j)).pt::x’ from ‘long long int’ to ‘double’ [-Wnarrowing]
  168 |                                         b.push_back(Segment({v[i].x,v[i].y}, {v[j].x,v[j].y}));
answer.code:168:91: warning: narrowing conversion of ‘v.std::vector<pt>::operator[](((std::vector<pt>::size_type)j)).pt::y’ from ‘long long int’ to ‘double’ [-Wnarrowing]
  168 |                                         b.push_back(Segment({v[i].x,v[i].y}, {v[j].x,v[j].y}));