QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#723271#9520. Concave HullcarottWA 1ms6816kbC++205.9kb2024-11-07 21:40:402024-11-07 21:40:48

Judging History

你现在查看的是最新测评结果

  • [2024-11-07 21:40:48]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6816kb
  • [2024-11-07 21:40:40]
  • 提交

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];

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];
    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];
        idx[v-1] = i;
    }
    if (n > 1) v --;
    for(int i=0; i<v; ++i) isin[idx[i]] = true; 
    return {n,v};
}

const int maxn = 100005;
Point p[maxn];
Point C[maxn];
int n;
void solve(){
    scanf("%d", &n);
    fill(isin, isin+n+5, false);
    for(int i=0; i<n; ++i) scanf("%lld%lld\n",&p[i].x, &p[i].y);
    pii tmp = andrew(p, C, n);
    // for(int i=0; i<n; ++i) cout<<p[i].x<<' '<<p[i].y<<endl;
    int cn = tmp.second;
    // cout<<"CONVEX::\n";
    // for(int i=0; i<cn; ++i) cout<<C[i].x<<' '<<C[i].y<<endl;
    // cout<<"-------------\n";
    n = tmp.first;
    vector<Point> notin;
    for(int i=0; i<n; ++i){
        if(!isin[i]) notin.push_back(p[i]);
    }
    if(notin.empty()){
        cout<<-1<<endl;
        return;
    }
    int m = notin.size();
    db sz = polygonarea(C, cn);
    // cout<<sz<<endl;
    db mns = inf;
    for(int i=0, j=0; i< cn;++i){
        while(-Cross(C[(i+1)%cn], C[i], notin[j])+Cross(C[(i+1)%n],C[i],notin[(j+1)%m]) > 0) j = (j+1)%m;
        mns = min(mns, -Cross(C[(i+1)%cn], C[i], notin[j]));
    }
    cout << sz - mns <<endl;
}

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: 1ms
memory: 6784kb

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: 1ms
memory: 6816kb

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:

2177958054552734781
1826413114144932145
1651566148755549130
1882491265383424105
2116880837269842460
894016174881844630
2270878897763509626
1998288626425286720
1740474221286618711
1163564929303947142

result:

wrong answer 1st lines differ - expected: '2178418010787347715', found: '2177958054552734781'