Submission #1089839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089839		vjudge1	Simurgh (IOI17_simurgh)	C++17	Compilation error	0 ms	0 KiB

simurgh

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define ll long long
#define ar array

const int INF = 1e18;
const int N = 2e3;
const int M = 1e7;
const int MOD = 1e9 + 7;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

struct P{
	int x, y, v;
	void read(){
		cin>>x>>y>>v;
	}
	
	P operator -(const P& b)const {
		return P{x - b.x, y - b.y};
	}
	void operator -= (const P& b){
		x -= b.x;
		y -= b.y;
	}
	int operator *(const P& b) const{
		return x * b.y - y * b.x;
	}
	
	int triangle(const P& b, const P& c){
		return (b - *this) * (c - *this);
	}
    int norm(){
        return x *x + y * y;
    }
};

bool intersect(P p1, P p2, P p3, P p4){
	if((p2 - p1) * (p4 - p3) == 0){
		if(p1.triangle(p2, p3) != 0){
			return 0;
		}
		bool b = false;
		for(int i = 0;i<2;i++){
			if(max(p1.x, p2.x) < min(p3.x, p4.x) || max(p1.y, p2.y) < min(p3.y, p4.y)){
				return 0;
			}
			swap(p1, p3);
			swap(p2, p4);
		}
		return 1;
	}
	bool b = false;
	for(int i = 0;i<2;i++){
		int s1 = p1.triangle(p2, p3);
		int s2 = p1.triangle(p2, p4);
		if((s1 < 0 && s2 < 0) || (s1 > 0 && s2 > 0)){
			return 0;
		}
		
		swap(p1, p3);
		swap(p2, p4);
	}
	
	return 1;
	
	
}
 
bool contains(P a, P b, P c){
	if(a.triangle(b, c) != 0){
		return false;
	}
	return min(a.x, b.x) <= c .x && c.x <= max(a.x, b.x) && min(a.y, b.y) <= c.y && c.y <= max(a.y, b.y);
}

int n;
P A[N];
int ans;
void get(vector<P> v){
    if(v.size() < 3)return;
    int m = v.size();
    vector<int> p;
    for(int i = 0;i < m;i++){
        int j = (i + 1) % m;
        int k = (i + 2) % m;
        p.push_back(v[i].triangle(v[j], v[k]));
    }
    for(auto u: p){
        if(u > 0 && p[0] < 0)return;
    }
    int res = 0;
    for(int i = 0;i < n;i++){
        auto p = A[i];
        P out = P{A[i].x + 1, 3000000000};
        bool b = 0;
        int c = 0;
        for(int i = 0;i < m;i++){
            int j = (i + 1) % m;
            if(contains(v[i], v[j], p)){
                b = 1;
                break;
            }
            if(intersect(p, out, v[i], v[j]))c++;
        }
        if(b || c % 2)res+=p.v;
    }
    ans = max(ans, res);
}

bool operator<(P x, P y){
    int t = x * y;
	return t != 0 ? t > 0 : x.norm() < y.norm();
}

signed main(){ios_base::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    for(int i = 0;i < n;i++)A[i].read();
    sort(A, A + n);
    ans = -INF;
    for(int i =0 ;i < (1 << n);i++){
        vector<P> v;
        for(int j = 0;j < n;j++){
            if((1 << j) & i)v.push_back(A[j]);
        }
        get(v);
    }
    cout<<ans;
}   

//! MI SE SPIEEEEE!

Compilation message (stderr)

simurgh.cpp: In function 'bool intersect(P, P, P, P)':
simurgh.cpp:47:8: warning: unused variable 'b' [-Wunused-variable]
   47 |   bool b = false;
      |        ^
simurgh.cpp:57:7: warning: unused variable 'b' [-Wunused-variable]
   57 |  bool b = false;
      |       ^
/usr/bin/ld: /tmp/cc9FUHzA.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccoWSSGC.o:simurgh.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc9FUHzA.o: in function `main':
grader.cpp:(.text.startup+0x2ef): undefined reference to `find_roads(int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status