Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Points Inside A Polygon CodeChef Solution
Problem -Points Inside A Polygon CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
<<Previous CodeChef Problem Next Codechef Problem>>
Points Inside A Polygon CodeChef Solution in C++14
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define eb emplace_back
#define ff first
#define ss second
#define nl '\n'
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
typedef long long ll;
typedef unsigned long long ulln;
template <class A, class B> ostream& operator << (ostream& out, const pair<A, B> &a) { return out << "(" << a.ff << ", " << a.ss << ")"; }
template <class A> ostream& operator << (ostream& out, const vector<A> &v) {
out << "["; for(int i=0; i<(int)v.size(); i++) { if(i) out << ", "; out << v[i]; } return out << "]"; }
string __debug_separator="\n";
#define deb_set(x) __debug_separator=x;
#define chk(a) cout<<(#a)<<" = "<<a<<endl;
#define debug(args...) \
{ \
string _ss = #args; \
replace(_ss.begin(), _ss.end(), ',', ' '); \
stringstream _ssm(_ss); \
istream_iterator<string> _it(_ssm); \
deb(_it, args); \
cout<<endl; \
}
void deb(istream_iterator<string> it)
{
}
template <typename T, typename... Args>
void deb(istream_iterator<string> it, T a, Args... args)
{
cout << *it << " = " << a << __debug_separator;
deb(++it, args...);
}
mt19937 mt_rand(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N = 5e5 + 5;
inline int dcmp (ll x) { if (x == 0) return 0; else return x < 0 ? -1 : 1; }
struct Point {
ll x, y;
Point (ll x = 0, ll y = 0): x(x), y(y) {}
bool operator == (const Point& u) const { return dcmp(x - u.x) == 0 && dcmp(y - u.y) == 0; }
bool operator != (const Point& u) const { return !(*this == u); }
bool operator < (const Point& u) const { return dcmp(x - u.x) < 0 || (dcmp(x-u.x)==0 && dcmp(y-u.y) < 0); }
bool operator > (const Point& u) const { return u < *this; }
bool operator <= (const Point& u) const { return *this < u || *this == u; }
bool operator >= (const Point& u) const { return *this > u || *this == u; }
Point operator + (const Point& u) { return Point(x + u.x, y + u.y); }
Point operator - (const Point& u) { return Point(x - u.x, y - u.y); }
Point operator * (const ll u) { return Point(x * u, y * u); }
Point operator / (const ll u) { return Point(x / u, y / u); }
ll operator * (const Point& u) { return x*u.y - y*u.x; }
};
typedef Point Vector;
ll getCross (Vector a, Vector b) { return a.x * b.y - a.y * b.x; }
ll getArea (Point a, Point b, Point c) { return abs(getCross(b - a, c - a)); }
bool pointInTriangle(Point a, Point b, Point c, Point p){
ll s1 = getArea(a,b,c);
ll s2 = getArea(p,b,c) + getArea(p,a,b) + getArea(p,c,a);
return dcmp(s1 - s2) == 0;
}
vector<Point> pt;
int pointInConvexPolygon(int n, Point p){
assert(n >= 3);
int lo = 1 , hi = n - 1 ;
while(hi - lo > 1){
int mid = (lo + hi) / 2;
if(getCross(pt[mid] - pt[0], p - pt[0]) > 0) lo = mid;
else hi = mid;
}
bool in = pointInTriangle(pt[0], pt[lo], pt[hi], p);
if(!in) return -1;
if(getCross(pt[lo] - pt[lo-1], p - pt[lo-1]) == 0) return 0;
if(getCross(pt[hi] - pt[lo], p - pt[lo]) == 0) return 0;
if(getCross(pt[hi] - pt[(hi+1)%n], p - pt[(hi+1)%n]) == 0) return 0;
return 1;
}
map<pair<ll, ll> , bool> mp;
int need;
int fx[] = {0, 0, 1, -1};
int fy[] = {1, -1, 0, 0};
void dfs(ll x, ll y)
{
if (mp.find({x, y}) != mp.end()) return;
if (mp.size() >= need) return;
mp[{x, y}] = true;
for (int i = 0; i < 4; i++)
{
auto z = Point(x + fx[i], y + fy[i]);
if (pointInConvexPolygon(pt.size(), z) == 1)
{
dfs(x + fx[i], y + fy[i]);
}
}
}
void solve()
{
int nn;
cin >> nn;
pt.clear();
ll mx = 0, my = 0;
for (int i = 0; i < nn; i++)
{
ll x, y;
cin >> x >> y;
mx += x, my += y;
pt.push_back(Point(x, y));
}
mp.clear();
need = nn / 10;
for (int p = 0; p < nn; p++)
{
for (int i = -1; i <= 1; i++)
{
for (int j = -1; j <= 1; j++)
{
int x = pt[p].x + i;
int y = pt[p].y + j;
if (pointInConvexPolygon(nn, Point(x, y)) == 1)
{
dfs(x, y);
}
}
}
}
if (mp.size() < need)
{
cout << -1 << nl;
return;
}
assert(mp.size() == need);
for (auto i: mp)
{
cout << i.ff.ff << ' ' << i.ff.ss << nl;
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);//cin.tie(NULL);cout.tie(NULL);
int q=1;
cin>>q;
for(int kase=1; kase<=q; kase++)
{
solve();
}
return 0;
}Points Inside A Polygon CodeChef Solution in PYTH 3
for _ in range(int(input())):
N = int(input())
points = [(tuple(map(int, input().split())), i) for i in range(N)]
sol = set()
for i in range(8):
po = list(filter(lambda x: x[0][0] % 2 == (i // 4) and x[0][1] % 2 == ((i // 2) % 2) \
and x[1] % 2 == (i % 2), points))
if len(po) > (N // 10):
for i in range(1, (N // 10) + 1):
print((po[i-1][0][0] + po[i][0][0]) // 2, (po[i-1][0][1] + po[i][0][1]) // 2)
breakPoints Inside A Polygon CodeChef Solution in C
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#define MXPOINT 100000
int FOUND = 0;
typedef struct point{
double x, y;
}Point;
double min(double a, double b){return a>b ? b : a;}
double max(double a, double b){return a<b ? b : a;}
double gcd(double a, double b){
while (a>0 && b>0){
if (a>b) a=((int)a)%((int)b);
else b=((int)b)%((int)a);
}
return max(a,b);
}
Point RESULT[MXPOINT];
void print_points(){
for(int i=0;i<FOUND;i++){
printf("%d %d\n",(int)RESULT[i].x,(int)RESULT[i].y);
}
}
int PRNT_LINE(Point p0,Point p1,int yet,int limit){
int res = yet;
double num=p1.y-p0.y;
double den=p1.x-p0.x;
double cd=gcd(num,den);
num/=cd;
den/=cd;
double y=p0.y;
for (double x = p0.x+den; x<p1.x ;x+=den){
y+=num;
Point tmp;//=malloc(sizeof(Point));
tmp.x=x;
tmp.y=y;
RESULT[FOUND++]=tmp;
res+=1;
if (res==limit) return res;
}
return res;
}
int PRNT_TRIANGL(Point p0,Point p1,Point p2, int yet,int limit,int strt,int end,int jump){
int res=yet;
double aD0=INT_MAX,aD1=INT_MAX,aD2=INT_MAX;
if (p1.x!=p0.x) aD0 = (p1.y-p0.y)/(p1.x-p0.x);
double bD0 = p0.y-aD0*p0.x;
if (p2.x!=p1.x) aD1 = (p2.y-p1.y)/(p2.x-p1.x);
double bD1 = p1.y-aD1*p1.x;
if (p0.x!=p2.x) aD2 = (p0.y-p2.y)/(p0.x-p2.x);
double bD2 = p2.y-aD2*p2.x;
int x=strt;
while (x!=end){
double D0=aD0*x+bD0;
double D1=aD1*x+bD1;
double D2=aD2*x+bD2;
double ly=0,hy=0,ly1=0,hy1=0,ly2=0,hy2=0;
if (p0.x<p1.x){
if (p2.x<p0.x){
ly1= (int)(floor(D2));ly2 = (int)(floor(D0)); hy=(int)(ceil(D1));
ly=max(ly1,ly2);
if (ly==INT_MAX)
ly=min(ly1,ly2);
}
else if (p2.x<p1.x){
ly=(int)(floor(D0)); hy1=(int)(ceil(D2)); hy2=(int)(ceil(D1));
hy=min(hy1,hy2);
}
else{
ly1=(int)(floor(D0));ly2=(int)(floor(D1));hy=(int)(ceil(D2));
ly=max(ly1,ly2);
if (ly==INT_MAX) ly=min(ly1,ly2);
}
}
else{
if (p2.x<p1.x){
ly=(int)(floor(D2));hy1=(int)(ceil(D1));hy2=(int)(ceil(D0));
hy=min(hy1,hy2);
}
else if (p2.x<p0.x){
ly1=(floor(D1));ly2=(floor(D2));hy=(ceil(D0));
ly=max(ly1,ly2);
if (ly==INT_MAX)
ly=min(ly1,ly2);
}
}
if (hy-ly+1<=2) break;
for(double y = ly+1; y<hy; y++){
Point tmp;//=malloc(sizeof(Point));
tmp.x=x;
tmp.y=y;
RESULT[FOUND++]=tmp;
res+=1;
if (res==limit)
return res;
}
x+=jump;
}
return res;
}
int main(){
int N,T;
scanf("%d",&T);
for(int testcase=0;testcase<T;testcase++){
FOUND=0;
scanf("%d",&N);
Point points[N];
Point tmp_point ;//= malloc(sizeof(Point));
for(int n=0;n<N;n++){
scanf("%lf",&tmp_point.x);
scanf("%lf",&tmp_point.y);
points[n]=tmp_point;
}
int DXM = N/10, total=0, i0=0;
for(int n=1;n<N;n++)
if (points[n].y<points[i0].y) i0=n;
Point p0 = points[i0];
for(int i=1;i<N-2;i++){
Point p1 = points[(i0+i)%N];
Point p2 = points[(i0+i+1)%N];
double lx = min(min(p0.x,p1.x),p2.x);
double hx = max(max(p0.x,p1.x),p2.x);
double mx = max(max(min(p0.x,p1.x),min(p0.x,p2.x)),min(p1.x,p2.x));
total = PRNT_TRIANGL(p0, p1, p2, total, DXM, mx-1, lx, -1);
if (total == DXM) {print_points(); break;}
total = PRNT_TRIANGL(p0, p1, p2, total, DXM, mx, hx, 1);
if (total == DXM) {print_points(); break;}
total = PRNT_LINE(p0,p2,total,DXM);
if (total == DXM) {print_points(); break;}
}
if (total == DXM) continue;
int i=N-2;
Point p1 = points[(i0+i)%N];
Point p2=points[(i0+i+1)%N];
double lx = min(min(p0.x,p1.x),p2.x);
double hx = max(max(p0.x,p1.x),p2.x);
double mx = max(max(min(p0.x,p1.x),min(p0.x,p2.x)),min(p1.x,p2.x));
total = PRNT_TRIANGL(p0, p1, p2, total, DXM, mx-1, lx, -1);
if (total == DXM) {print_points(); continue;}
total = PRNT_TRIANGL(p0, p1, p2, total, DXM, mx, hx, 1);
if (total == DXM) print_points();
else printf("-1\n");
}
return 0;
}Points Inside A Polygon CodeChef Solution in JAVA
import java.util.HashSet;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Set;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int test = sc.nextInt();
while (test-- > 0) {
int flag = 0, aa, bb, yy;
int size1 = 0;
double fx, fy;
Set<String> actual = new HashSet<String>();
Set<String> err = new HashSet<String>();
int n = sc.nextInt();
double[] c = new double[2 * n + 2];
int cc = (int) Math.floor(n / 10);
for (int i = 1; i < 2 * n + 1; i += 2) {
c[i] = sc.nextInt();
c[i + 1] = sc.nextInt();
err.add((int) c[i] + " " + (int) c[i + 1]);
}
for (int i = 1; i < n - 1; i++) {
for (int j = 1; j <= 2 * n; j += 2) {
for (int k = 0; k < 7; k += 2) {
aa = j;
bb = (j + 2 * i) % (2 * n);
yy = (j + 4 * i + k) % (2 * n);
fx = (c[aa] + c[bb] + c[yy]) / 3;
fy = (c[aa + 1] + c[bb + 1] + c[yy + 1]) / 3;
if (fx == Math.floor(fx) && fy == Math.floor(fy)) {
size1 = err.size();
err.add((int) fx + " " + (int) fy);
if (err.size() != size1) {
actual.add((int) fx + " " + (int) fy);
}
if (actual.size() == cc) {
flag = 1;
break;
}
}
}
if (flag == 1) {
break;
}
}
if (flag == 1) {
break;
}
}
Iterator<String> ir = actual.iterator();
if (actual.size() >= cc) {
for (int i = 0; i < cc; i++) {
System.out.println(ir.next());
}
} else {
System.out.println("-1");
}
}
}
}Points Inside A Polygon CodeChef Solution in PYTH
for _ in range(input()):
n = input()
p = [None] * n
par = {
(0, 0): [],
(0, 1): [],
(1, 0): [],
(1, 1): []
}
for i in range(n):
x, y = map(int, raw_input().split())
p[i] = (x, y)
par[(abs(x) % 2, abs(y) % 2)].append(i)
m = par[(0, 1)]
for v in par.values():
if len(v) > len(m): m = v
i = 0
r = set()
for i, a in enumerate(m):
for j in range(i + 1, len(m)):
b = m[j]
if a + 1 == b: continue
if a == 0 and b == n - 1: continue
r.add(((p[a][0] + p[b][0]) / 2, (p[a][1] + p[b][1]) / 2))
if len(r) == n / 10: break
if len(r) == n / 10: break
for x, y in r:
print x, yPoints Inside A Polygon CodeChef Solution in C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace PolygonCodechefFeb
{
class Program
{
static HashSet<long> done = new HashSet<long>();
static long max = 0, min = 0;
static double computeIntercept(Tuple<long, long> p1, Tuple<long, long> p2, long y)
{
//double inverseslope = (double)(p1.Item1 - p2.Item1) / (double)(p1.Item2 - p2.Item2);
return ((double)(p1.Item1 - p2.Item1) / (double)(p1.Item2 - p2.Item2) * (double)(y - p1.Item2) + p1.Item1);
}
static double computeIntercept2(double x1, double y1, double x2, double y2, double y)
{
//double inverseslope = (x1 - x2) / (y1 - y2);
return ((x1 - x2) / (y1 - y2) * (y - y1) + x1);
}
static HashSet<Tuple<long, long>> iterate(int n, HashSet<Tuple<long, long>> insidePoints, double lx1, double ly1, double rx1, double ry1, double lx2, double ly2, double rx2, double ry2)
{
double rintercept, lintercept;
long rceil, lceil;
for (long y = (long)ly1; y >= (long)ly2; y--)
{
if (y == max || y == min)
continue;
if (done.Contains(y))
continue;
done.Add(y);
lintercept = computeIntercept2(lx1, ly1, lx2, ly2, y);
rintercept = computeIntercept2(rx1, ry1, rx2, ry2, y);
lceil = (long)Math.Ceiling(lintercept) == lintercept ? (long)lintercept + 1 : (long)Math.Ceiling(lintercept);
rceil = (long)Math.Floor(rintercept) == rintercept ? (long)rintercept - 1 : (long)Math.Floor(rintercept);
//Console.WriteLine("Intercept : {0} {1}", lintercept, rintercept);
//Console.WriteLine("Intercept : {0} {1}", lceil, rceil);
for (long x = lceil; x <= rceil; x++)
{
insidePoints.Add(new Tuple<long, long>(x, y));
//Console.WriteLine("Down : {0} {1}", x, y);
if (insidePoints.Count == n / 10)
break;
}
if (insidePoints.Count == n / 10)
break;
}
return insidePoints;
}
static void Main(string[] args)
{
string read;
int testCases, n;
testCases = int.Parse(Console.ReadLine());
List<Tuple<long, long>> Points = new List<Tuple<long, long>>();
List<Tuple<long, long>> Left = new List<Tuple<long, long>>();
List<Tuple<long, long>> Right = new List<Tuple<long, long>>();
HashSet<Tuple<long, long>> insidePoints = new HashSet<Tuple<long, long>>();
while (testCases-- > 0)
{
long item1, item2;
max = min = 0;
int maxYPoint = 0, minYPoint = 0, rightindex, leftindex;
bool firstFlag = true;
read = Console.ReadLine();
n = int.Parse(read);
Points.Clear(); Left.Clear(); Right.Clear(); insidePoints.Clear(); done.Clear();
for (int i = 0; i < n; i++)
{
read = Console.ReadLine();
item1 = long.Parse(read.Split(' ').ToList()[0]);
item2 = long.Parse(read.Split(' ').ToList()[1]);
Tuple<long, long> tuple = new Tuple<long, long>(item1, item2);
Points.Add(tuple);
if (firstFlag)
{
firstFlag = false;
max = min = item2;
maxYPoint = minYPoint = i;
}
else if (max < item2)
{
max = item2;
maxYPoint = i;
}
else if (min > item2)
{
min = item2;
minYPoint = i;
}
}
rightindex = leftindex = maxYPoint;
//if (maxYPoint > minYPoint)
{
while (rightindex != minYPoint)
{
Right.Add(Points[rightindex]);
rightindex = rightindex - 1;
if (rightindex == -1)
rightindex = n - 1;
}
Right.Add(Points[minYPoint]);
while (leftindex != minYPoint)
{
Left.Add(Points[leftindex]);
leftindex = (leftindex + 1) % n;
}
Left.Add(Points[minYPoint]);
}
/*
if (maxYPoint < minYPoint)
{
while (rightindex != minYPoint)
{
Right.Add(Points[rightindex]);
rightindex = (rightindex + 1) % n;
}
Right.Add(Points[minYPoint]);
while (leftindex != minYPoint)
{
Left.Add(Points[leftindex]);
leftindex = (leftindex - 1);
if (leftindex == -1)
leftindex = n - 1;
}
Left.Add(Points[minYPoint]);
}*/
Tuple<long, long> rightFirst = new Tuple<long, long>(Right[0].Item1, Right[0].Item2);
Tuple<long, long> rightSecond = new Tuple<long, long>(Right[1].Item1, Right[1].Item2);
int rightEnd = 1;
Tuple<long, long> leftFirst = new Tuple<long, long>(Left[0].Item1, Left[0].Item2);
Tuple<long, long> leftSecond = new Tuple<long, long>(Left[1].Item1, Left[1].Item2);
int leftEnd = 1;
double intercept = 0.0;
double previousleftx = 0.0, previouslefty = 0.0, currentleftx = 0.0, currentlefty = 0.0;
double previousrightx = 0.0, previousrighty = 0.0, currentrightx = 0.0, currentrighty = 0.0;
previousleftx = previousrightx = Points[maxYPoint].Item1;
previouslefty = previousrighty = Points[maxYPoint].Item2;
int select = 1;
while (true)
{
//Console.WriteLine("pre");
//Console.WriteLine("Left : {0},{1} {2},{3}", leftFirst.Item1, leftFirst.Item2, leftSecond.Item1, leftSecond.Item2);
//Console.WriteLine("Right : {0},{1} {2},{3}", rightFirst.Item1, rightFirst.Item2, rightSecond.Item1, rightSecond.Item2);
if (rightFirst.Item2 == rightSecond.Item2)
{
if (rightSecond == Right.Last())
{
break;
}
++rightEnd;
rightFirst = rightSecond;
rightSecond = Right[rightEnd];
previousrightx = rightFirst.Item1;
previousrighty = rightFirst.Item2;
continue;
}
if (leftFirst.Item2 == leftSecond.Item2)
{
if (leftSecond == Left.Last())
{
break;
}
++leftEnd;
leftFirst = leftSecond;
leftSecond = Left[leftEnd];
previousleftx = leftFirst.Item1;
previouslefty = leftFirst.Item2;
continue;
}
if (leftSecond.Item2 > rightSecond.Item2)
{
intercept = computeIntercept(rightFirst, rightSecond, leftSecond.Item2);
currentleftx = leftSecond.Item1;
currentlefty = currentrighty = leftSecond.Item2;
currentrightx = intercept;
select = 1;
}
else if (leftSecond.Item2 < rightSecond.Item2)
{
intercept = computeIntercept(leftFirst, leftSecond, rightSecond.Item2);
currentrightx = rightSecond.Item1;
currentlefty = currentrighty = rightSecond.Item2;
currentleftx = intercept;
select = 2;
}
else if (leftSecond.Item2 == rightSecond.Item2)
{
currentlefty = currentrighty = leftSecond.Item2;
currentrightx = rightSecond.Item1;
currentleftx = leftSecond.Item1;
select = 3;
}
/*Console.WriteLine("post");
Console.WriteLine("Left : {0},{1} {2},{3}", leftFirst.Item1, leftFirst.Item2, leftSecond.Item1, leftSecond.Item2);
Console.WriteLine("Right : {0},{1} {2},{3}", rightFirst.Item1, rightFirst.Item2, rightSecond.Item1, rightSecond.Item2);
Console.WriteLine("Previous : {0},{1} {2},{3}", previousleftx, previouslefty, previousrightx, previousrighty);
Console.WriteLine("Current : {0},{1} {2},{3}", currentleftx, currentlefty, currentrightx, currentrighty);*/
insidePoints = iterate(n, insidePoints, previousleftx, previouslefty, previousrightx, previousrighty, currentleftx, currentlefty, currentrightx, currentrighty);
previousleftx = currentleftx;
previouslefty = currentlefty;
previousrightx = currentrightx;
previousrighty = currentrighty;
if (insidePoints.Count == n / 10)
break;
if (select == 1)
{
if (leftSecond == Left.Last())
{
break;
}
++leftEnd;
leftFirst = leftSecond;
leftSecond = Left.ElementAt(leftEnd);
}
if (select == 2)
{
if (rightSecond == Right.Last())
{
break;
}
++rightEnd;
rightFirst = rightSecond;
rightSecond = Right.ElementAt(rightEnd);
}
if (select == 3)
{
if (leftSecond == Left.Last() || rightSecond == Right.Last())
{
break;
}
++leftEnd;
leftFirst = leftSecond;
leftSecond = Left.ElementAt(leftEnd);
++rightEnd;
rightFirst = rightSecond;
rightSecond = Right.ElementAt(rightEnd);
}
}
if (insidePoints.Count == n / 10)
{
foreach (var p in insidePoints)
{
Console.WriteLine("{0} {1}", p.Item1, p.Item2);
}
}
else
{
Console.WriteLine(-1);
//Console.WriteLine(insidePoints.Count);
}
//Console.WriteLine(insidePoints.Count);
}
}
}
}Points Inside A Polygon CodeChef Solution in GO
package main
import (
"bufio"
"fmt"
"os"
"sort"
)
func main() {
scanner := bufio.NewScanner(os.Stdin)
tc := readNum(scanner)
for tc > 0 {
n := readNum(scanner)
points := make([][]int, n)
for i := 0; i < n; i++ {
points[i] = readNNums(scanner, 2)
}
res := solve(n, points)
for _, ans := range res {
fmt.Printf("%d %d\n", ans[0], ans[1])
}
tc--
}
}
func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] != ' ' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}
func readNum(scanner *bufio.Scanner) (a int) {
scanner.Scan()
readInt(scanner.Bytes(), 0, &a)
return
}
func readTwoNums(scanner *bufio.Scanner) (a int, b int) {
res := readNNums(scanner, 2)
a, b = res[0], res[1]
return
}
func readNNums(scanner *bufio.Scanner, n int) []int {
res := make([]int, n)
x := 0
scanner.Scan()
for i := 0; i < n; i++ {
for x < len(scanner.Bytes()) && scanner.Bytes()[x] == ' ' {
x++
}
x = readInt(scanner.Bytes(), x, &res[i])
}
return res
}
func solve(n int, points [][]int) [][]int {
ps := make(Points, n)
for i := 0; i < n; i++ {
ps[i] = Point{points[i][0], points[i][1]}
}
sort.Sort(ps)
findHull := func(lower bool) Points {
sign := 1
if lower {
sign = -1
}
res := make(Points, n)
var idx int
for i := 0; i < n; i++ {
for idx >= 2 && cross(res[idx-2], res[idx-1], ps[i])*sign >= 0 {
idx--
}
res[idx] = ps[i]
idx++
}
return res[:idx]
}
upper := findHull(false)
lower := findHull(true)
checkGood := func(hull Points, p Point, lower bool) bool {
sign := 1
if !lower {
sign = -1
}
it := sort.Search(len(hull), func(i int) bool {
return hull[i].x >= p.x
})
if it == len(hull) || it == 0 {
return false
}
res := sign * cross(hull[it-1], hull[it], p)
return res > 0
}
inside := func(p Point) bool {
return checkGood(lower, p, true) && checkGood(upper, p, false)
}
var p0 Point
for i := 2; i < n; i++ {
p0.x = (ps[0].x + ps[i].x) / 2
p0.y = (ps[0].y + ps[i].y) / 2
if inside(p0) {
break
}
}
que := make([]Point, n/10+4)
front, end := 0, 0
que[end] = p0
end++
checked := make(map[Point]bool)
checked[p0] = true
for end < n/10 && front < end {
u := que[front]
front++
vs := []Point{
Point{u.x - 1, u.y},
Point{u.x + 1, u.y},
Point{u.x, u.y - 1},
Point{u.x, u.y + 1},
}
for _, v := range vs {
if !checked[v] && inside(v) {
checked[v] = true
que[end] = v
end++
}
}
}
res := make([][]int, n/10)
for i := 0; i < n/10; i++ {
res[i] = []int{que[i].x, que[i].y}
}
return res
}
func solve1(n int, points [][]int) [][]int {
set := make(map[Point]bool)
for i := 0; len(set) < n/10; i += 9 {
for j := i; j < i+9 && j < n; j++ {
for k := j + 2; k < i+9 && k < n; k++ {
a, b := points[j], points[k]
if (a[0]+b[0])%2 == 0 && (a[1]+b[1])%2 == 0 {
set[Point{(a[0] + b[0]) / 2, (a[1] + b[1]) / 2}] = true
}
}
}
}
res := make([][]int, len(set))
var idx int
for p := range set {
res[idx] = []int{p.x, p.y}
idx++
}
return res[:n/10]
}
type Point struct {
x, y int
}
func (this Point) Sub(that Point) Point {
return Point{this.x - that.x, this.y - that.y}
}
func cross(a, b, c Point) int {
ab := b.Sub(a)
bc := c.Sub(b)
x := int64(ab.x) * int64(bc.y)
y := int64(ab.y) * int64(bc.x)
if x > y {
return 1
} else if x < y {
return -1
}
return 0
}
type Points []Point
func (ps Points) Len() int {
return len(ps)
}
func (ps Points) Less(i, j int) bool {
return ps[i].x < ps[j].x || (ps[i].x == ps[j].x && ps[i].y < ps[j].y)
}
func (ps Points) Swap(i, j int) {
ps[i], ps[j] = ps[j], ps[i]
}Points Inside A Polygon CodeChef Solution Review:
In our experience, we suggest you solve this Points Inside A Polygon CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Points Inside A Polygon CodeChef Solution.
Conclusion:
I hope this Points Inside A Polygon CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
