Topic

Bessie, Farmer John's prize cow, has just won first place in a bovine beauty contest, earning the title 'Miss Cow World'. As a result, Bessie will make a tour of N (2 <= N <= 50,000) farms around the world in order to spread goodwill between farmers and their cows. For simplicity, the world will be represented as a two-dimensional plane, where each farm is located at a pair of integer coordinates (x,y), each having a value in the range -10,000 ... 10,000. No two farms share the same pair of coordinates.

Even though Bessie travels directly in a straight line between pairs of farms, the distance between some farms can be quite large, so she wants to bring a suitcase full of hay with her so she has enough food to eat on each leg of her journey. Since Bessie refills her suitcase at every farm she visits, she wants to determine the maximum possible distance she might need to travel so she knows the size of suitcase she must bring.Help Bessie by computing the maximum distance among all pairs of farms.

Input

  • Line 1: A single integer, N

  • Lines 2..N+1: Two space-separated integers x and y specifying coordinate of each farm

Output

  • Line 1: A single integer that is the squared distance between the pair of farms that are farthest apart from each other.

Sample Input

4

0 0

0 1

1 1

1 0

Sample Output

2

Hint

Farm 1 (0, 0) and farm 3 (1, 1) have the longest distance (square root of 2)

Answer key

The main idea of the topic : Give the coordinates of some farms , Find the square of the linear distance between the farthest farms .

Answer key :

First, the convex hull is obtained by scanning , Rotate the chuck to get the maximum value


#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
#define MAX 50010
#define INF 1000000000
#define rg register
inline int read()
{
int x=0,t=1;char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
if(ch=='-'){t=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*t;
}
struct Node
{
int x,y;
}p[MAX],p0,S[MAX];
int n,top,T;
inline bool cmp(Node a,Node b)
{
rg double A=atan2(a.y-p0.y,a.x-p0.x);
rg double B=atan2(b.y-p0.y,b.x-p0.x);
if(A!=B)return A<B;
else return a.x<b.x;
}
inline long long chaji(int x1,int y1,int x2,int y2)// Calculate the cross product
{
return (1LL*x1*y2-1LL*x2*y1);
}
inline long long Compare(Node a,Node b,Node c)// Calculate the vector
{
return chaji((b.x-a.x),(b.y-a.y),(c.x-a.x),(c.y-a.y));
}
inline void Find()// Looking for convex hull
{
p0=(Node){INF,INF};
rg int k=0;
for(rg int i=0;i<n;++i)// Find the bottom point
if(p0.y>p[i].y||(p0.y==p[i].y&&p0.x>p[i].x))
p0=p[i],k=i;
swap(p[k],p[0]);
sort(&p[1],&p[n],cmp);// About sorting the bottom points
S[0]=p[0];S[1]=p[1];
top=1;// To the top of the stack
for(rg int i=2;i<n;)// Find the convex hull
{
if(top&&Compare(S[top-1],p[i],S[top])>=0) top--;
else S[++top]=p[i++];
}
}
inline long long Dis(Node a,Node b)// Calculate the sum of the squares of the distances between two points
{
return 1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y);
}
long long GetMax()// Find the diameter
{
rg long long re=0;
if(top==1)// There are only two points
return Dis(S[0],S[1]);
S[++top]=S[0];// Put the first point at the end
int j=2;
for(int i=0;i<top;++i)// Enumerate edges
{
while(Compare(S[i],S[i+1],S[j])<Compare(S[i],S[i+1],S[j+1]))
j=(j+1)%top;
re=max(re,max(Dis(S[i],S[j]),Dis(S[i+1],S[j])));
}
return re; }
int main()
{
n=read();
for(int i=0;i<n;++i)
{
p[i].x=read();p[i].y=read();
}
long long ans=INF,ss;
Find();
ans=GetMax();
cout<<ans<<endl;
return 0;
}

POJ 2187 Beauty Contest( convex hull , Spin the cartridge ) More articles about

  1. POJ 2187 - Beauty Contest - [ convex hull + Rotating chuck method ][ The diameter of the convex hull ]

    Topic link :http://poj.org/problem?id=2187 Time Limit: 3000MS Memory Limit: 65536K Description Bessie, Farm ...

  2. POJ 2187 Beauty Contest [ convex hull Spin the cartridge ]

    Beauty Contest Time Limit: 3000MS   Memory Limit: 65536K Total Submissions: 36113   Accepted: 11204 ...

  3. POJ 2187 Beauty Contest【 To find the diameter of convex hull by rotating the chuck 】

    link : http://poj.org/problem?id=2187 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=22013#probl ...

  4. poj 2187 Beauty Contest( Convex hull solves the maximum distance between nodes )

    /* poj 2187 Beauty Contest convex hull : Find the maximum distance between each two points The maximum value must be on the edge of the convex hull ! The algorithm for finding convex hull : Andrew Algorithm ! */ #include<iostr ...

  5. 【POJ】2187 Beauty Contest( Spin the cartridge )

    http://poj.org/problem?id=2187 Obviously the diameter is on the convex hull ( There's proof in the black book ).( Then this question let me find that I have been wrong several times before QAQ Just sort x Axis ..... There is no order y Axis .. Then the data of this problem ...

  6. POJ 2187 Beauty Contest convex hull

    Beauty Contest Time Limit: 3000MS   Memory Limit: 65536K Total Submissions: 27276   Accepted: 8432 D ...

  7. Beauty Contest convex hull + Rotating chuck method

    Beauty Contest Time Limit: 3000MS   Memory Limit: 65536K Total Submissions: 27507   Accepted: 8493 D ...

  8. 【POJ 2187】Beauty Contest convex hull + Spin the cartridge

    xuán zhuǎn qiǎ ké The template questions That's how you read it (≖ ‿ ≖)* The algorithm is very simple : Just find the right heel , Update the answer by the way . #include<cstdio> #include<cstring&g ...

  9. poj 2187 Beauty Contest Convex hull template + Find the farthest point

    Topic link The question : Here you are. n Coordinates of points ,n<=50000, Find the farthest point #include <iostream> #include <cstdio> #include <cs ...

  10. poj 2187 Beauty Contest( Two dimensional convex hull rotating chuck )

    D - Beauty Contest Time Limit:3000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u ...

Random recommendation

  1. The finger of the sword offer Interview questions 64 Median of data flow

    struct cmp { bool operator()(double a, double b) { return a > b; } }; class Solution { public: vo ...

  2. Ubuntu 14.04 Next Sogou input method crash restart

    pidof fcitx | xargs kill pidof sogou-qimpanel | xargs kill nohup fcitx >/dev/>/dev/null & ...

  3. eclipse Install in adt plug-in unit

    For program developers ,eclipse No stranger , It provides us with a very broad platform to develop programs . We can also use it to develop android Program . But in eclipse It can't be developed directly in android Program , We need to ...

  4. jquery Delete array elements

    expertsId.splice($.inArray(thisID.split('&')[0],expertsId),1); 1. expertsId Array name 2. thisID.split('& ...

  5. 1.5 understand Analyzers,Tokenizers,Filters-- Catalog

    This part introduces solr How to decompose and process text data , It contains the following topics : 1.5.1 Analyzers,Tokenizers,Filters summary : This paper mainly introduces Analyzers,Tokenizers,Filter ...

  6. Reprint C# Middle pile (heap) And the stack (stack) The difference between

    Reprint the original address   http://www.cnblogs.com/wangshenhe/archive/2013/02/18/2916275.html [ turn ]C# The difference between heap and stack Understanding heaps and stacks is important for understanding .NET Medium ...

  7. Wechat applet to get the verification code js

    How to realize the countdown function of obtaining verification code in wechat applet , The principle of countdown is the same , It's something that needs to be noticed . First step : structure <view class='get-code' wx:if="{{!isS ...

  8. poj1185 State compression classic problem

    State compression is a good problem , Direct calculation of burst memory , First of all, find out all the possible states stk in , then f[i][k][t] Express i The row status is t,i-1 Status as k, from i-1 State to launch i Status can be Pay attention to the state of marginal conditions , And some feasible state ...

  9. python Code check for

    #!/bin/python3.4# coding=utf-8 class lexicon(object): # direction = ['north', 'south', 'east', 'west ...

  10. Linux Serial port programming under the receiving data errors encountered and the reasons (0x0d,0x11 Receive error )

    Abstract :Linux Serial port programming under the receiving data errors encountered and the reasons source :https://dotblogs.com.tw/k/2012/07/24/73572 Recently, when debugging the serial port, I found that , Another device came to me ARM The serial port of the board sends ...