QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#796499#9520. Concave HullxixuCompile Error//C++205.1kb2024-12-01 19:55:162024-12-01 19:55:16

Judging History

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

  • [2024-12-01 19:55:16]
  • 评测
查看
  • [2024-12-01 19:55:16]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
// #pragma GCC optimize(2)
#define int long long
// #define int __int128
#define double long long
// #define double __int128
// #define ull __int128
#define re read()
#define pr(x) print(x)
#define fup(a, b, c, d) for(int a = (b); a <= (c); a += (d))
#define fdown(a, b, c, d) for(int a = (b); a >= (c); a -= (d))
#define sq(x) (x) * (x)
// #define read() re
#define write(x) w(x)
typedef long long ll;
// typedef unsigned long long ull;
typedef pair<int , int> PII;
typedef map<int , int> MII;
const int inf = 0x3f3f3f3f, N = 2e6 + 10, M = 4e5 + 10, mod = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;

char *p1,*p2,buf[100000];
#define nc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)

int read()
{
    int x=0,f=1;
    char ch=nc();
    while(ch<48||ch>57)
    {
        if(ch=='-')
            f=-1;
        ch=nc();
    }
    while(ch>=48&&ch<=57)
        x=x*10+ch-48,ch=nc();
   	return x*f;
}

void write(__int128 x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
	// printf("\n");
    return;
}


__int128 s(double x1, double y1, double x2, double y2, double x3, double y3) 
{
	return ((__int128)x1 * y2 + (__int128)x2 * y3 + (__int128)x3 * y1 - (__int128)x1 * y3 - (__int128)x2 * y1 - (__int128)x3 * y2);
}

void solve(){
    struct point{
        double x,y;
        point operator+(point a)const{
            return {x+a.x,y+a.y};
        }
        point operator-(point a)const{
            return {x-a.x,y-a.y};
        }
        point operator*(double a)const{
            return {a*x,a*y};
        }
        double operator*(point a)const{
            return x*a.y-y*a.x;
        }
        double operator&(point a)const{
            return x*a.x+y*a.y;
        }
        bool operator==(point a){
            if(x==a.x&&y==a.y)return true;
            return false;
        }
		bool operator<(point a)const{
            if(x!=a.x)return x<a.x;
            return y<a.y;
        }
        point rot(double t) const { // 逆时针
            return {x*cos(t)-y*sin(t),x*sin(t)+y*cos(t)};
        }
        point rot90() const {
            return {-y,x};
        }
        double len2() const {
            return x*x+y*y;
        }
        double len() const {
            return sqrt(x*x+y*y);
        }
    };
    auto dis=[&](point a,point b)->double{
        return sqrt(sq(a.x-b.x)+sq(a.y-b.y));
    };
    auto check=[&](point a,point b,point c)->bool{
        return ((a.x-b.x)*(a.y-c.y)-(a.y-b.y)*(a.x-c.x))<=0;
    };
    auto Convex_Hull=[&](vector<point>po,int si)->stack<point>{
        sort(po.begin(),po.end());
        stack<point>s;
        int size=0;
        s.push(po[0]);
        for(int i=1;i<=si-1;i++){
            point c=po[i];
            while(size){
                point b=s.top();
                s.pop();
                point a=s.top();
                s.push(b);
                if(check(a,b,c)){
                    size--;
                    s.pop();
                }else break;
 
            }
            s.push(c);
            size++;
        }
        size=0;
        for(int i=si-2;~i;i--){
            point c=po[i];
            while(size){
                point b=s.top();
                s.pop();
                point a=s.top();
                s.push(b);
                if(check(a,b,c)){
                    size--;
                    s.pop();
                }else break;
 
            }
            s.push(c);
            size++;
        }
        if(s.size()==1)s.push(po[0]);
        return s;
    };
	int n;
	n = read();
	vector<point> po(n);
	for(auto &[x,y] : po) {
		x = read(), y = read();
	}
	// cout << 0;
	// return ;
	stack<point> stk = Convex_Hull(po, n);
	
	if(n <= 3) {
		w(-1);
		printf("\n");
		return ;
	}
	vector<point> v1, v2;
	map<point, int> mp;
	while(stk.size()) {
		auto t = stk.top();
		stk.pop();
		if(!mp[t])
		v1.push_back(t);
		// cout << t.x << ' ' << t.y << '\n';
		mp[t] ++;
	}
	if(v1.size() == n) {
		w(-1);
		printf("\n");
		return ;
	}
	// cout << '\n';
	for(auto t : po) {
		// cout << t.x << ' ' << t.y << '\n';
		if(mp[t]) continue ;

		v2.push_back(t);
	}
	// cout << '\n';
	// return ;
	// cout << v2.size() << '\n';
	stk = Convex_Hull(v2, v2.size());
	v2.clear();
	
	// cout << stk.size() << '\n';
	// return ;

	while(stk.size()) {
		auto t = stk.top();
		stk.pop();
		v2.push_back(t);
	}

	__int128 mi = INF;
	__int128 su = 0;
	point p = v1[0];
	fup(i, 1, v1.size() - 1, 1) {
		auto x1 = v1[i - 1], x2 = v1[i];
		for(auto x3 : v2) {
			mi = min(mi, (__int128)abs(s(x1.x, x1.y, x2.x, x2.y, x3.x, x3.y)));
		}
		if(i == 1) continue ;
		su += (__int128)abs(s(x1.x, x1.y, x2.x, x2.y, p.x, p.y));
	}
	// cout << mi << ' ' << su << '\n';
	w(su - mi);
	printf("\n");
	
}

signed main()
{
    // cin.tie(0);
    // cout.tie(0);
    // ios::sync_with_stdio(false);

    int _ = 1;
	_ = read();
    while(_ --)
    {
        solve();
    }
}
源文件, 语言: C++20

详细 

answer.code: In member function ‘solve()::point solve()::point::rot(long long int) const’:
answer.code:85:29: warning: narrowing conversion of ‘(((__gnu_cxx::__enable_if<true, double>::__type)(long long int)((const solve::point*)this)->solve::point::x * std::cos<long long int>(t)) - ((__gnu_cxx::__enable_if<true, double>::__type)(long long int)((const solve::point*)this)->solve::point::y * std::sin<long long int>(t)))’ from ‘__gnu_cxx::__enable_if<true, double>::__type’ {aka ‘double’} to ‘long long int’ [-Wnarrowing]
   85 |             return {x*cos(t)-y*sin(t),x*sin(t)+y*cos(t)};
      |                     ~~~~~~~~^~~~~~~~~
answer.code:85:47: warning: narrowing conversion of ‘(((__gnu_cxx::__enable_if<true, double>::__type)(long long int)((const solve::point*)this)->solve::point::x * std::sin<long long int>(t)) + ((__gnu_cxx::__enable_if<true, double>::__type)(long long int)((const solve::point*)this)->solve::point::y * std::cos<long long int>(t)))’ from ‘__gnu_cxx::__enable_if<true, double>::__type’ {aka ‘double’} to ‘long long int’ [-Wnarrowing]
   85 |             return {x*cos(t)-y*sin(t),x*sin(t)+y*cos(t)};
      |                                       ~~~~~~~~^~~~~~~~~
answer.code: In function ‘void solve()’:
answer.code:202:51: error: call of overloaded ‘abs(__int128)’ is ambiguous
  202 |                         mi = min(mi, (__int128)abs(s(x1.x, x1.y, x2.x, x2.y, x3.x, x3.y)));
      |                                                ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/cstdlib:79,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:42,
                 from answer.code:1:
/usr/include/stdlib.h:840:12: note: candidate: ‘int abs(int)’
  840 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
In file included from /usr/include/c++/13/cstdlib:81:
/usr/include/c++/13/bits/std_abs.h:79:3: note: candidate: ‘constexpr long double std::abs(long double)’
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:75:3: note: candidate: ‘constexpr float std::abs(float)’
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:71:3: note: candidate: ‘constexpr double std::abs(double)’
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:61:3: note: candidate: ‘long long int std::abs(long long int)’
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:56:3: note: candidate: ‘long int std::abs(long int)’
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
answer.code:205:36: error: call of overloaded ‘abs(__int128)’ is ambiguous
  205 |                 su += (__int128)abs(s(x1.x, x1.y, x2.x, x2.y, p.x, p.y));
      |                                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/stdlib.h:840:12: note: candidate: ‘int abs(int)’
  840 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
/usr/include/c++/13/bits/std_abs.h:79:3: note: candidate: ‘constexpr long double std::abs(long double)’
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:75:3: note: candidate: ‘constexpr float std::abs(float)’
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:71:3: note: candidate: ‘constexpr double std::abs(double)’
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:61:3: note: candidate: ‘long long int std::abs(long long int)’
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:56:3: note: candidate: ‘long int std::abs(long int)’
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
English 繁體中文 简体中文

服务器时间: 2024-12-04 07:31:42 | 开源项目