QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#723389 | #9520. Concave Hull | carott | WA | 2ms | 8644kb | C++20 | 5.7kb | 2024-11-07 22:03:10 | 2024-11-07 22:03:10 |
Judging History
answer
//Created by carottx on 2024-11-07.
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#include <random>
using namespace std;
#define db ll
typedef long long ll;
const db eps = 0;
const db inf = 1e18;
const db INF = 1e18;
typedef pair<int,int> pii;
const db PI = acos(-1.0);
inline int sgn(db x) {return x < 0 ? -1 : x>0;}
inline db sqr(db x) { return x*x; }
inline db mysqrt(db x) { return sqrt(max(0ll, x)); }
/*========================================================*\
| Point 类
| 类内函数
| Point(P x = 0, P y = 0) - 默认构造函数
| input() - 读入一个点
| operator == - NULL
| operator < - 用于排序
| operator + - 返回Point
| operator - - 返回Point
| operator * - 返回Point
| operator / - 返回Point
| len() - 返回长度
| len2() - 返回长度平方
| trunc(db len) - 长度变为len
| rotleft() - 逆时针转π/2, 返回Point
| rotright() - 顺时针转π/2, 返回Point
| rotate(P p, db ang) - 绕p逆时针转ang
| 类外函数
| *基础功能
| Cross(P a, P b) - NULL
| Cross(P pt, P a, P b) - NULL
| Dot(P a, P b) - NULL
| Dot(P pt, P a, P b) - NULL
| Dist(P a, P b) - NULL
| Len(a) - 返回a的长度
| Len2(a) - 返回a的长度平方
| rad(P p, P a, P b) - 返回∠apb
| Complex类补充
\*========================================================*/
struct Point {
db x, y;
Point (db x=0, db y=0): x(x), y(y) {}
void input() { scanf("%lld%lld", &x, &y); }
bool operator == (const Point& r) const{ return x==r.x && y==r.y==0; }
// bool operator < (Point r) { return sgn(x-r.x)==0 ? y < r.y : x < r.x; }
Point operator + (Point r) { return Point (x+r.x, y+r.y); }
Point operator - (Point r) { return Point (x-r.x, y-r.y); }
Point operator * (db r) { return Point (x*r, y*r); }
Point operator / (db r) { return Point (x/r, y/r); }
db len() { return mysqrt(x*x+y*y); }
db len2() { return x*x + y*y; }
// 化为长度为 r 的向量
// Point trunc(db len) {
// db l = mysqrt(x * x + y * y);
// if (! sgn(l)) return *this;
// len /= l;
// return Point (x*len, y*len);
// }
// 逆时针旋转 90 度
Point rotleft() { return Point (-y, x); }
// 顺时针旋转 90 度
Point rotright() { return Point (y, -x); }
// 绕着 p 点逆时针旋转 ang
// Point rotate (Point p, db ang) {
// Point v = (*this) - p;
// db c = cos(ang), s = sin(ang);
// return Point (p.x + v.x*c - v.y*s, p.y + v.x*s + v.y*c);
// }
};
db Cross (Point a, Point b) { return a.x*b.y - a.y*b.x; }
db Cross (Point pt, Point a, Point b) { return (Cross(a-pt, b-pt)); }
db Dot (Point a, Point b) { return a.x*b.x + a.y*b.y; }
db Dot (Point pt, Point a, Point b) { return Dot (a-pt, b-pt); }
db Dist (Point a, Point b) { return mysqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }
db Len (Point a) { return mysqrt(a.x*a.x + a.y*a.y); }
db Len2 (Point a) { return a.x*a.x + a.y*a.y; }
db polygonarea(Point* p, int n) {
db ans = 0;
p[n] = p[0];
for (int i = 0; i < n; i ++)
ans += Cross(p[i], p[i+1]);
return ans; // 面积有正负, 需根据题意来判断要不要取绝对值
}
bool operator < (const Point& a, const Point& b) {
if (a.y==b.y) return a.x < b.x;
return a.y < b.y;
}
// bool isin[100005];
map<Point, bool> mp;
db abscross(Point pt, Point a, Point b) {return abs(Cross(pt, a,b));}
pii andrew(Point *p, Point *ch, int n) { // 返回值是凸包的顶点数
// static int idx[100005];
// memcpy(p, tmp, sizeof(Point) * n);
// fill(idx, idx+n+5, -1);
sort (p, p + n); // 排序
n = unique(p, p + n) - p; // 去除重复的点
int v = 0;
for (int i = 0; i < n; i ++) {
while (v > 1 && Cross(ch[v-2], ch[v-1], p[i]) <= 0) v --;
ch[v++] = p[i];
// idx[v-1] = i;
}
int j = v;
// 求上凸包
for (int i = n - 2; i >= 0; i --) {
while (v > j && Cross(ch[v-2], ch[v-1], p[i]) <= 0) v --;
ch[v ++] = p[i];
}
if (n > 1) v --;
for(int i=0; i<v; ++i) mp[ch[i]] = true;
return {n,v};
}
const int maxn = 100005;
Point p[maxn];
Point ttmp[maxn];
Point C[maxn];
int n;
void solve(){
mp.clear();
scanf("%d", &n);
for(int i=0; i<n; ++i) scanf("%lld%lld\n",&p[i].x, &p[i].y);
memcpy(ttmp, p, sizeof(Point) * n);
pii tmp = andrew(ttmp, C, n);
int cn = tmp.second;
// n = tmp.first;
vector<Point> notin;
for(int i=0; i<n; ++i){
if(!mp[p[i]]) notin.push_back(p[i]);
}
if(notin.empty()){
puts("-1");
return;
}
int m = notin.size();
db sz = polygonarea(C, cn);
db mns = sz;
for(int i=0, j=0; i< cn;++i){
while(Cross(C[i], C[(i+1)%cn], notin[j])-Cross(C[i],C[(i+1)%cn],notin[(j+1)%m]) > 0) j = (j+1)%m;
mns = min(mns, Cross(C[i], C[(i+1)%cn], notin[j]));
}
printf("%lld\n", sz-mns);
}
int main(){
// freopen("result.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 8516kb
input:
2 6 -2 0 1 -2 5 2 0 4 1 2 3 1 4 0 0 1 0 0 1 1 1
output:
40 -1
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 8644kb
input:
10 243 -494423502 -591557038 -493438474 -648991734 -493289308 -656152126 -491185085 -661710614 -489063449 -666925265 -464265894 -709944049 -447472922 -737242534 -415977509 -773788538 -394263365 -797285016 -382728841 -807396819 -373481975 -814685302 -368242265 -818267002 -344482838 -833805545 -279398...
output:
2178414095795486749 1826413114144932145 1651587424867450109 1882491265383424105 2119126281997959892 894016174881844630 2271166497746806577 1998643358049669416 1740474221286618711 1168195646932543192
result:
wrong answer 1st lines differ - expected: '2178418010787347715', found: '2178414095795486749'