Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Johny the farmer CodeChef Solution
Problem -Johny the farmer 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.
Johny the farmer CodeChef Solution in C++17
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ll> vll;
#define all(v) v.begin(),v.end()
#define sz(x) (int)(x).size()
#define alr(v) v.rbegin(),v.rend()
#define pb push_back
#define S second
#define F first
#define pow2(x) (1<<(x))
#define sp(x) cout<<fixed<<setprecision(6)<<x
#define output(x) cout<<(x?"YES\n":"NO\n")
#define bp(x) __builtin_popcount(x)
//#define int long long
template<class T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).
template<typename T>
void uniq(vector<T> &v) { sort(all(v)); v.resize(unique(all(v)) - v.begin()); }
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
const int N=1e6+1;
const char nl='\n';
const ll mod=1e9+7;
const ll Binf=1e18;
const ll mod1=998244353;
struct point {
ll x, y;
point() {}
point(ll x, ll y): x(x), y(y) {}
bool operator==(const point &t)
{
return (x==t.x && y==t.y);
}
bool operator<(const point& p) const
{
return x < p.x || ((x == p.x) && y < p.y );
}
};
//clockwise : right turn
bool cw(point a, point b, point c) {
return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) <= 0;
}
//counter-clockwise : left turn
bool ccw(point a, point b, point c) {
return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) >= 0;
}
//Andrew's Algorithm
void convex_hull(vector<point> & a)
{
point p1 = a[0],p2=a.back();
vector<point> up,down;
int n = a.size();
up.push_back(p1),down.push_back(p1);
for(int i=1;i<n;i++)
{
if (i == (int)a.size() - 1 || cw(p1, a[i], p2))
{
while (up.size() >= 2 && !cw(up[up.size()-2], up[up.size()-1], a[i]))
up.pop_back();
up.push_back(a[i]);
}
if (i == (int)a.size() - 1 || ccw(p1, a[i], p2))
{
while(down.size() >= 2 && !ccw(down[down.size()-2], down[down.size()-1], a[i]))
down.pop_back();
down.push_back(a[i]);
}
}
a.clear();
for (int i = 0; i < (int)up.size(); i++)
a.push_back(up[i]);
for (int i = down.size() - 2; i > 0; i--)
a.push_back(down[i]);
}
ll area(point & a,point & b,point & c)
{
int res = 0;
res = (a.x - b.x)*(a.y + b.y) + (b.x - c.x)*(b.y + c.y) + (c.x - a.x)*(c.y + a.y);
return abs(res);
}
ll max_area(vector<point> v){
if(sz(v)<3){
return 0;
}
int a=0,b=1,c=2,A=0,B=1,C=2;
int n=sz(v);
do{
for(;;){
while(area(v[a],v[b],v[c])<=area(v[a],v[b],v[(c+1)%n])) c=(c+1)%n;
if(area(v[a],v[b],v[c])<=area(v[a],v[(b+1)%n],v[c])) b=(b+1)%n;
else break;
}
if(area(v[a],v[b],v[c])>area(v[A],v[B],v[C])) A=a,B=b,C=c;
a=(a+1)%n;
if(a==b) b=(b+1)%n;
if(c==b) c=(c+1)%n;
}while(a!=0);
return area(v[A],v[B],v[C]);
}
void solve101(){
int n;
cin>>n;
vector<point> v(n);
for(int i=0;i<n;i++){
cin>>v[i].x>>v[i].y;
}
uniq(v);
convex_hull(v);
cout<<max_area(v)<<nl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
for(int i=1;i<=t;i++){
// cout<<"Case #"<<i<<": ";
solve101();
}
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
return 0;
}
// always check for binary search >.<
// #ifndef ONLINE_JUDGE
// if (fopen("input.txt", "r"))
// {
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// }
// #endifJohny the farmer CodeChef Solution in C++14
#include <cstdio>
#include <cstring>
#include <algorithm>
#define BUF 4096
struct Point {
int x, y;
};
Point p[1000000];
char ibuf[BUF];
int ipt;
int readInt() {
int s = 1;
while (ipt < BUF && ibuf[ipt] < '-') ipt++;
if (ipt == BUF) {
fread(ibuf, 1, BUF, stdin);
ipt = 0;
while (ipt < BUF && ibuf[ipt] < '-') ipt++;
}
if (ipt < BUF && ibuf[ipt] == '-') { s = -1; ipt++; }
int n = 0;
while (ipt < BUF && ibuf[ipt] >= '0') n = (n*10)+(ibuf[ipt++]-'0');
if (ipt == BUF) {
fread(ibuf, 1, BUF, stdin);
ipt = 0;
while (ipt < BUF && ibuf[ipt] >= '0') n = (n*10)+(ibuf[ipt++]-'0');
}
return n*s;
}
inline void swapPoints(int i, int j) {
int s;
s = p[i].x; p[i].x = p[j].x; p[j].x = s;
s = p[i].y; p[i].y = p[j].y; p[j].y = s;
}
inline int ccw(const Point &p1, const Point &p2, const Point &p3) {
return (p2.x-p1.x)*(p3.y-p1.y) - (p2.y-p1.y)*(p3.x-p1.x);
}
inline int dist2(const Point &p1, const Point &p2) {
return (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y);
}
inline bool scot(const Point &p1, const Point &p2) {
int c = ccw(p[0], p1, p2);
return c > 0 || (c == 0 && dist2(p[0], p1) < dist2(p[0], p2));
}
int grahamScan(int n) {
if (!n) return 0;
int nx = p[0].x, ny = p[0].y, ni = 0;
for (int i = 1; i < n; i++) if (p[i].y < ny || (p[i].y == ny && p[i].x < nx)) {
ny = p[i].y;
nx = p[i].x;
ni = i;
}
swapPoints(0, ni);
std::sort(p+1, p+n, scot);
int m = 1;
for (int i = 2; i < n; i++) {
while (m && ccw(p[m-1], p[m], p[i]) <= 0) m--;
swapPoints(++m, i);
}
return m+1;
}
int cutPoints(int n) {
Point xx = p[0], nx = p[0], xy = p[0], ny = p[0],
xxpy = p[0], nxpy = p[0], xxmy = p[0], nxmy = p[0];
for (int i = 0; i < n; i++) {
if (p[i].x > xx.x || (p[i].x == xx.x && abs(p[i].y) < abs(xx.y))) xx = p[i];
if (p[i].x < nx.x || (p[i].x == nx.x && abs(p[i].y) < abs(nx.y))) nx = p[i];
if (p[i].y > xy.y || (p[i].y == xy.y && abs(p[i].x) < abs(xy.x))) xy = p[i];
if (p[i].y < ny.y || (p[i].y == ny.y && abs(p[i].x) < abs(ny.x))) ny = p[i];
if (p[i].x+p[i].y > xxpy.x+xxpy.y) xxpy = p[i];
if (p[i].x+p[i].y < nxpy.x+nxpy.y) nxpy = p[i];
if (p[i].x-p[i].y > xxmy.x-xxmy.y) xxmy = p[i];
if (p[i].x-p[i].y < nxmy.x-nxmy.y) nxmy = p[i];
}
int m = 0;
for (int i = 0; i < n; i++) {
if (!(ccw(ny, xxmy, p[i]) > 0 && ccw(xxmy, xx, p[i]) > 0 &&
ccw(xx, xxpy, p[i]) > 0 && ccw(xxpy, xy, p[i]) > 0 &&
ccw(xy, nxmy, p[i]) > 0 && ccw(nxmy, nx, p[i]) > 0 &&
ccw(nx, nxpy, p[i]) > 0 && ccw(nxpy, ny, p[i]) > 0)) {
if (m < i) p[m] = p[i];
m++;
}
}
return m;
}
int ternary(int i, int j, int n) {
int lf = j, rt = n-1;
while (rt-lf > 2) {
int lth = (lf*2+rt)/3, rth = (lf+2*rt)/3;
if (abs(ccw(p[i], p[j], p[lth])) < abs(ccw(p[i], p[j], p[rth])))
lf = lth;
else
rt = rth;
}
int mx = 0;
for (int k = lf; k <= rt; k++) {
int a = abs(ccw(p[i], p[j], p[k]));
if (a > mx) mx = a;
}
return mx;
}
int main() {
int t = readInt();
for (int i = 0; i < t; i++) {
int n = readInt();
for (int j = 0; j < n; j++) {
p[j].x = readInt();
p[j].y = readInt();
}
if (n > 1500) {
int nn = cutPoints(n);
n = nn;
}
int ct = grahamScan(n);
int mxa = 0;
for (int j = 0; j < ct; j++)
for (int k = j+1; k < ct; k++) {
int a = ternary(j, k, ct);
if (a > mxa) mxa = a;
}
printf("%d\n", mxa);
}//p
return 0;
} Johny the farmer CodeChef Solution in C
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int x;
int y;
double cot;
int infinity;
} point;
#define area(a, b, c) (abs((b->x - a->x) * (c->y - a->y) - \
(c->x - a->x) * (b->y - a->y)))
#define ccw(p1, p2, p3) ((p2->x - p1->x) * (p3->y - p1->y) - \
(p2->y - p1->y) * (p3->x - p1->x))
int point_cmp(point **p1, point **p2)
{
if ((*p1)->infinity || (*p2)->infinity) {
return (*p2)->infinity - (*p1)->infinity;
}
if ((*p1)->cot > (*p2)->cot) {
return -1;
} else if ((*p1)->cot < (*p2)->cot) {
return 1;
}
else {
return 0;
}
}
int graham(int n, point **points) {
int m;
int i;
/* Compute polar angles (cot values) for all points with
* points[0] as origin. */
for (i = 1; i < n; i++) {
int x = points[i]->x - points[0]->x;
int y = points[i]->y - points[0]->y;
if (y == 0) {
points[i]->infinity = x;
} else {
points[i]->infinity = 0;
points[i]->cot = (double) x / y;
}
}
/* Sort the points based on the polar angles */
qsort(points + 1, n - 1, sizeof(point *),
(int (*)(const void *, const void *)) point_cmp);
if (n < 3)
return n;
m = 1;
for (i = 2; i < n; i++) {
int dir;
// If there is a right turn or collinear point and we are not
// dealing with the first three points, then backtracking logic
// will take care of doing the right thing.
while ((dir = ccw(points[m - 1], points[m], points[i])) <= 0 && m > 1) {
m--;
}
// If three collinear points are present, we must be dealing
// with the first three points as m > 1 has been taken care of
// above. Backtracking logic fails in this rare scenario. The
// following is the right thing to do.
if (dir == 0) {
int dist_m = (points[m]->x - points[m - 1]->x) *
(points[m]->x - points[m - 1]->x) +
(points[m]->y - points[m - 1]->y) *
(points[m]->y - points[m - 1]->y);
int dist_i = (points[i]->x - points[m - 1]->x) *
(points[i]->x - points[m - 1]->x) +
(points[i]->y - points[m - 1]->y) *
(points[i]->y - points[m - 1]->y);
if (dist_m < dist_i) {
// temp = points[m];
points[m] = points[i];
// points[i] = temp;
}
} else {
m++;
// temp = points[m];
points[m] = points[i];
// points[i] = temp;
}
}
// Finally, check whether the last two points and the starting point
// are collinear. If they are, forget the last point. However, if
// there are only two points, don't remove it.
if (ccw(points[m - 1], points[m], points[0]) <= 0 && m > 1) {
m--;
}
return m + 1;
}
void maximum_area(int n, point **p) {
int i;
int j;
int m;
int max_area = 0;
m = graham(n, p);
/* For each A */
for (i = 0; i <= m - 3; i++) {
point *a = p[i];
int zenith = i + 2;
/* For each B */
for (j = i + 1; j <= m - 2; j++) {
point *b = p[j];
int max_area_for_base = 0;
int k;
/* Point AB form a base. For this base, we will find a point
* C such that is at a maximum distance from the base AB. */
for (k = zenith; k <= m - 1; k++) {
int am = area(a, b, p[k]);
/* If C has degraded, last C was the best. */
if (am <= max_area_for_base) {
zenith = k - 1;
break;
}
max_area_for_base = am;
}
if (k == m) {
zenith = m - 1;
}
if (max_area_for_base > max_area) {
max_area = max_area_for_base;
}
}
}
printf("%d\n", max_area);
}
point p[1000000];
point *q[1000000];
int main()
{
int tests;
int n;
int i, j;
point temp;
scanf("%d", &tests);
for (i = 0; i < tests; i++) {
point p0;
int p_index;
scanf("%d", &n);
scanf("%d %d", &p[0].x, &p[0].y);
p0 = p[0];
q[0] = &p[0];
p_index = 0;
for (j = 1; j < n; j++) {
scanf("%d %d", &p[j].x, &p[j].y);
q[j] = &p[j];
if (p[j].y < p0.y) {
p0 = p[j];
p_index = j;
}
else if (p[j].y == p0.y && p[j].x < p0.x) {
p0 = p[j];
p_index = j;
}
}
temp = p0;
p[p_index] = p[0];
p[0] = temp;
if (n < 3) {
printf("0\n");
continue;
}
maximum_area(n, q);
}
return 0;
}
Johny the farmer CodeChef Solution in JAVA
import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader consoleReader = new BufferedReader(new InputStreamReader(System.in));
int testCases = Integer.parseInt(consoleReader.readLine());
int best,curr=0;
while (testCases > 0) {
int n = Integer.parseInt(consoleReader.readLine());
String str = consoleReader.readLine();
StringTokenizer st = new StringTokenizer(str," ");
int x=0;
int y=0;
Point pset[] = new Point[n];
for(int i=0;i<n;i++){
x = Integer.parseInt(st.nextToken());
y = Integer.parseInt(st.nextToken());
pset[i] = new Point(x,y);
}
Arrays.sort(pset,new PointComparator());
Point pcopy[] = new Point[n];
for(int i=0;i<n;i++){
pcopy[i] = new Point(pset[i].x,pset[i].y);
}
int convexEnd=0;
try{
for(int i=1;i<n;i++){
while(convexEnd > 0 && (crossproduct(pcopy[convexEnd-1],pcopy[convexEnd],pset[i])<=0))
convexEnd--;
convexEnd++;
pcopy[convexEnd].x = pset[i].x;
pcopy[convexEnd].y = pset[i].y;
}
int len = convexEnd;
for(int i=n-2;i>=1;i--){
while(convexEnd>len && (crossproduct(pcopy[convexEnd-1],pcopy[convexEnd],pset[i])<=0))
convexEnd--;
convexEnd++;
pcopy[convexEnd].x = pset[i].x;
pcopy[convexEnd].y = pset[i].y;
}
n = convexEnd+1;
}catch(Exception e){}
best=0;
int take=0;
for(int i=0;i<n;i++){
curr=0;
for(int j=i+2;j<n;j++){
int tcurr = Math.abs(crossproduct(pcopy[i],pcopy[i+1],pcopy[j]));
if(tcurr>curr){
curr = tcurr;
take=j;
}
}
best = Math.max(curr,best);
for(int j=i+2;j<n;j++){
while((take<n-1) &&(Math.abs(crossproduct(pcopy[i],pcopy[j],pcopy[take]))<=crossproduct(pcopy[i],pcopy[j],pcopy[take+1])))
take++;
curr=Math.abs(crossproduct(pcopy[i],pcopy[j],pcopy[take]));
best = Math.max(curr,best);
}
}
System.out.println(best);
testCases--;
}
}
static int crossproduct(Point A,Point B,Point C){
return ((B.x-A.x)*(C.y-A.y))-((C.x-A.x)*(B.y-A.y));
}
}
class PointComparator implements Comparator<Point>{
public int compare(Point o1, Point o2) {
int i=o1.x - o2.x;
if(i==0)
return o1.y - o2.y;
else
return i;
}
}Johny the farmer CodeChef Solution in GO
package main
import (
"bufio"
"bytes"
"fmt"
"os"
"sort"
)
func main() {
reader := bufio.NewReader(os.Stdin)
var buf bytes.Buffer
tc := readNum(reader)
for tc > 0 {
tc--
n := readNum(reader)
P := readNNums(reader, 2*n)
res := solve(n, P)
buf.WriteString(fmt.Sprintf("%d\n", res))
}
fmt.Print(buf.String())
}
func readUint64(bytes []byte, from int, val *uint64) int {
i := from
var tmp uint64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp
return i
}
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] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}
func readString(reader *bufio.Reader) string {
s, _ := reader.ReadString('\n')
for i := 0; i < len(s); i++ {
if s[i] == '\n' {
return s[:i]
}
}
return s
}
func readNum(reader *bufio.Reader) (a int) {
bs, _ := reader.ReadBytes('\n')
readInt(bs, 0, &a)
return
}
func readTwoNums(reader *bufio.Reader) (a int, b int) {
res := readNNums(reader, 2)
a, b = res[0], res[1]
return
}
func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
res := readNNums(reader, 3)
a, b, c = res[0], res[1], res[2]
return
}
func readNNums(reader *bufio.Reader, n int) []int {
res := make([]int, n)
x := 0
bs, _ := reader.ReadBytes('\n')
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
x = readInt(bs, x, &res[i])
}
return res
}
func solve(n int, P []int) int {
points := make([]Point, n)
for i := 0; i < n; i++ {
points[i] = NewPoint(P[2*i], P[2*i+1])
}
sort.Sort(Points(points))
hull := make([]Point, 2*n)
var pos int
hull[pos] = points[0]
pos++
for i := 1; i < n; i++ {
cur := points[i]
for pos >= 2 && (cur.Sub(hull[pos-2]).Cross(cur.Sub(hull[pos-1]))) >= 0 {
pos--
}
hull[pos] = cur
pos++
}
start := pos - 1
for i := n - 2; i >= 0; i-- {
cur := points[i]
for pos-start >= 2 && (cur.Sub(hull[pos-2]).Cross(cur.Sub(hull[pos-1]))) >= 0 {
pos--
}
hull[pos] = cur
pos++
}
pos--
var ans int
for i := 0; i < pos; i++ {
j := (i + 1) % pos
k := (j + 1) % pos
for k != i && area(hull[i], hull[j], hull[k]) < area(hull[i], hull[j], hull[(k+1)%pos]) {
k = (k + 1) % pos
}
if k == i {
continue
}
kk := (k + 1) % pos
for j != kk && k != i {
ans = max(ans, area(hull[i], hull[j], hull[k]))
for k != i && area(hull[i], hull[j], hull[k]) < area(hull[i], hull[j], hull[(k+1)%pos]) {
k = (k + 1) % pos
}
j = (j + 1) % pos
}
}
return ans
}
func max(a, b int) int {
if a >= b {
return a
}
return b
}
type Point struct {
x int
y int
}
func NewPoint(x, y int) Point {
return Point{x, y}
}
func (this Point) Less(that Point) bool {
return this.x < that.x || this.x == that.x && this.y < that.y
}
func (this Point) Sub(that Point) Point {
return NewPoint(this.x-that.x, this.y-that.y)
}
func (this Point) Cross(that Point) int {
return this.x*that.y - this.y*that.x
}
func area(a, b, c Point) int {
return abs(b.Sub(a).Cross(c.Sub(a)))
}
func abs(num int) int {
if num < 0 {
return -num
}
return num
}
type Points []Point
func (this Points) Len() int {
return len(this)
}
func (this Points) Less(i, j int) bool {
return this[i].Less(this[j])
}
func (this Points) Swap(i, j int) {
this[i], this[j] = this[j], this[i]
}Johny the farmer CodeChef Solution Review:
In our experience, we suggest you solve this Johny the farmer 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 Johny the farmer CodeChef Solution.
Conclusion:
I hope this Johny the farmer 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!
