| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1089839 | vjudge1 | Simurgh (IOI17_simurgh) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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!