如何计算XI Samara区域大学生编程竞赛B题的最小面积问题？
- 内容介绍
- 文章标签
- 相关推荐
本文共计806个文字，预计阅读时间需要4分钟。
您希望将以下内容简化并修改，字数不超过100字：
Given a strictly convex polygon, compute the minimal possible area of a non-degenerate triangle formed by its vertices. Input: The first line contains an integer n (3 ≤ n ≤ 200000) — the number of vertices of the polygon.
修改后的内容：给定一严格凸多边形，求由其顶点构成的非退化三角形的可能最小面积。输入：第一行一个整数n（3≤n≤200000）—多边形的顶点数。
You are given a strictly convex polygon. Find the minimal possible area of non-degenerate triangle whose
vertices are the vertices of the polygon.
Input
The first line contains a single integer n (3 ≤ n ≤ 200000) — the number of polygon vertices.
Each of the next n lines contains two integers xi and yi (−109 ≤ xi
, yi ≤ 109
) — the coordinates of polygon
vertices.
The polygon is guaranteed to be strictly convex. Vertices are given in the counterclockwise order.
Output
It is known that the area of triangle whose vertices are the integer points on the grid is either integer or
half-integer.
Output a single integer — the required area, multiplied by 2.
Examples
standard input standard output
4
0 1
3 0
3 3
-1 3
5
3
0 0
1 0
0 1
1
4
-999999991 999999992
-999999993 -999999994
999999995 -999999996
999999997 999999998
3999999948000000156
Note
It is recommended to make all calculations using integer numbers, because floating point precision most
likely would not be enough.
这次计算几何还挺简单的；
题意：给定一个严格凸多边形，求在凸多边形中找三个点，使得构成的三角形面积最小；
最后输出答案*2；
很明显是相邻的三个点组成的面积最小。。。。。那么只需要绕一圈即可
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
#include<ctime>
#include<deque>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 500005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const long long int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-7
#define pll pair<ll,ll>
ll quickpow(ll a, ll b) {
ll ans = 1;
a = a % mod;
while (b > 0) {
if (b % 2)ans = ans * a;
b = b / 2;
a = a * a;
}
return ans;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
bool prime(int x) {
if (x == 0 || x == 1)return false;
for (int i = 2; i <= sqrt(x); i++) {
if (x%i == 0)return false;
}
return true;
}
ll x[maxn], y[maxn];
ll ans = 5e18 + 1;
ll work(ll x1, ll y1, ll x2, ll y2) {
return abs((ll)x1*y2 - (ll)x2 * y1);
}
int main()
{
ios::sync_with_stdio(false);
int n; cin >> n;
int i, j;
for (i = 0; i < n; i++)cin >> x[i] >> y[i];
x[n] = x[0]; x[n + 1] = x[1];
y[n] = y[0]; y[n + 1] = y[1];
for (i = 0; i < n; i++) {
ans = min(ans, work(x[i] - x[i + 1], y[i] - y[i + 1], x[i] - x[i + 2], y[i] - y[i + 2]));
}
cout << ans << endl;
}
本文共计806个文字，预计阅读时间需要4分钟。
您希望将以下内容简化并修改，字数不超过100字：
Given a strictly convex polygon, compute the minimal possible area of a non-degenerate triangle formed by its vertices. Input: The first line contains an integer n (3 ≤ n ≤ 200000) — the number of vertices of the polygon.
修改后的内容：给定一严格凸多边形，求由其顶点构成的非退化三角形的可能最小面积。输入：第一行一个整数n（3≤n≤200000）—多边形的顶点数。
You are given a strictly convex polygon. Find the minimal possible area of non-degenerate triangle whose
vertices are the vertices of the polygon.
Input
The first line contains a single integer n (3 ≤ n ≤ 200000) — the number of polygon vertices.
Each of the next n lines contains two integers xi and yi (−109 ≤ xi
, yi ≤ 109
) — the coordinates of polygon
vertices.
The polygon is guaranteed to be strictly convex. Vertices are given in the counterclockwise order.
Output
It is known that the area of triangle whose vertices are the integer points on the grid is either integer or
half-integer.
Output a single integer — the required area, multiplied by 2.
Examples
standard input standard output
4
0 1
3 0
3 3
-1 3
5
3
0 0
1 0
0 1
1
4
-999999991 999999992
-999999993 -999999994
999999995 -999999996
999999997 999999998
3999999948000000156
Note
It is recommended to make all calculations using integer numbers, because floating point precision most
likely would not be enough.
这次计算几何还挺简单的；
题意：给定一个严格凸多边形，求在凸多边形中找三个点，使得构成的三角形面积最小；
最后输出答案*2；
很明显是相邻的三个点组成的面积最小。。。。。那么只需要绕一圈即可
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<bitset>
#include<ctime>
#include<deque>
typedef long long ll;
using namespace std;
typedef unsigned long long int ull;
#define maxn 500005
#define ms(x) memset(x,0,sizeof(x))
#define Inf 0x7fffffff
#define inf 0x3f3f3f3f
const long long int mod = 1e9 + 7;
#define pi acos(-1.0)
#define pii pair<int,int>
#define eps 1e-7
#define pll pair<ll,ll>
ll quickpow(ll a, ll b) {
ll ans = 1;
a = a % mod;
while (b > 0) {
if (b % 2)ans = ans * a;
b = b / 2;
a = a * a;
}
return ans;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
bool prime(int x) {
if (x == 0 || x == 1)return false;
for (int i = 2; i <= sqrt(x); i++) {
if (x%i == 0)return false;
}
return true;
}
ll x[maxn], y[maxn];
ll ans = 5e18 + 1;
ll work(ll x1, ll y1, ll x2, ll y2) {
return abs((ll)x1*y2 - (ll)x2 * y1);
}
int main()
{
ios::sync_with_stdio(false);
int n; cin >> n;
int i, j;
for (i = 0; i < n; i++)cin >> x[i] >> y[i];
x[n] = x[0]; x[n + 1] = x[1];
y[n] = y[0]; y[n + 1] = y[1];
for (i = 0; i < n; i++) {
ans = min(ans, work(x[i] - x[i + 1], y[i] - y[i + 1], x[i] - x[i + 2], y[i] - y[i + 2]));
}
cout << ans << endl;
}