/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 332.0 KiB
#2 Wrong Answer 1ms 540.0 KiB
#3 Accepted 2ms 368.0 KiB
#4 Accepted 2ms 508.0 KiB
#5 Wrong Answer 1ms 768.0 KiB

Code

//SUST_ZadeedBoss_Fanclub
//code_korlei_life_ase
//na_korle_lifeNai

#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T> using o_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
#define VPT vector <PT>
#define double long double
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); 
#define eps 1e-9
struct PT
{
	double x, y;
	PT() {x=0, y=0;}
	PT (int _x, int _y) : x(_x), y(_y) {}

	PT operator- (const PT &a) const
	{
		return PT(x-a.x, y-a.y);
	}
};
int sign(int x)
{
	return (x > eps) - (x < -eps);
}
double cross (PT a, PT b)
{
	return a.x * b.y - a.y * b.x;
}
int orientation (PT a, PT b, PT c)
{
	return sign(cross(b-a, c-a));
}
bool is_point_on_seg (PT a, PT b, PT p)
{
	if (abs(cross(p - b, a-b)) < eps)
	{
		if (p.x<min(a.x,b.x) || p.x > max(a.x,b.x))return 0;
		if (p.y<min(a.y,b.y) || p.y > max(a.y,b.y))return 0;
		return 1;
	}
	return 0;
}
bool is_point_on_polygon(VPT &p,const PT& z)
{
	int n = p.size();
	for(int i=0;i<n;i++)
	{
		if(is_point_on_seg(p[i],p[(i+1)%n],z))
		{
			return 1;
		}
	}
	return 0;
}
int winding_number(VPT &p,const PT& z)
{

	int n =p.size(),ans=0;
	// cout <<n <<" ";
	if(is_point_on_polygon(p,z))
	{
		return 1e9;
	}
	for(int i=0;i<n;i++)
	{
		int j = (i + 1)%n;
		bool below = p[i].y < z.y;
		if(below!=(p[j].y < z.y))
		{
			auto orient = orientation(z, p[j], p[i]);
			// cout <<i <<" " <<below <<" " <<orient <<"o\n";
			if (orient==0)return 0;
			if (below == orient && below)
				if (below) ans++;
				else ans--;

			
		}

	}
	return ans;
}
int is_point_in_polygon(VPT &p,const PT& z)
{
	int k = winding_number(p,z);
	if (k == 1e9) return 0;
	if (k == 0) return 1;
	return -1;
}
void solve ()
{

	int n; cin >>n;
	vector <PT> inp(n);
	for (auto &it : inp)
	{
		int x,y; cin >>x >>y;
		it= PT(x, y);
	}
	int x, y; cin >>x >>y;
	PT p = PT(x, y);
	if (is_point_in_polygon(inp, p) == 1) cout <<"YES\n";
	else cout <<"NO\n";
}

signed main()
{

	ios_base::sync_with_stdio(0);
	cin.tie(NULL);

	int TCASE = 1;
	// cin >> TCASE;

	for (int tcase = 1; tcase <= TCASE; tcase++)
	{
		solve();
	}

}

Information

Submit By
Type
Submission
Problem
P1145 Nobita's Love for Shizuka
Contest
LU IUJPC : Sylhet Division 2024
Language
C++17 (G++ 13.2.0)
Submit At
2024-12-09 08:54:46
Judged At
2024-12-09 08:54:46
Judged By
Score
8
Total Time
2ms
Peak Memory
768.0 KiB